Converting nondeterministic two-way automata into small deterministic linear-time machines
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00362443" target="_blank" >RIV/68407700:21230/22:00362443 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.ic.2022.104938" target="_blank" >https://doi.org/10.1016/j.ic.2022.104938</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2022.104938" target="_blank" >10.1016/j.ic.2022.104938</a>
Alternative languages
Result language
angličtina
Original language name
Converting nondeterministic two-way automata into small deterministic linear-time machines
Original language description
In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases, while it remains open in general, the best upper bound currently known being exponential. We present a new approach in which unrestricted nondeterministic automata are simulated by deterministic models extending two-way deterministic automata, paying only a polynomial increase of size. Indeed, we study the costs of the conversions of nondeterministic automata into some variants of one-tape deterministic Turing machines working in linear time; namely Hennie machines, weight-reducing Turing machines, and weight-reducing Hennie machines. All these variants are known to share the same computational power: they characterize the class of regular languages.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-21198S" target="_blank" >GA19-21198S: Complex prediction models and their learning from weakly annotated data</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation
ISSN
0890-5401
e-ISSN
1090-2651
Volume of the periodical
289
Issue of the periodical within the volume
November
Country of publishing house
US - UNITED STATES
Number of pages
11
Pages from-to
—
UT code for WoS article
000914897100007
EID of the result in the Scopus database
2-s2.0-85134208657