Converting nondeterministic two-way automata into small deterministic linear-time machines

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Converting nondeterministic two-way automata into small deterministic linear-time machines

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Converting nondeterministic two-way automata into small deterministic linear-time machines

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-21198S" target="_blank" >GA19-21198S: Složité predikční modely a jejich učení z částečně anotovaných dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information and Computation

ISSN

0890-5401

e-ISSN

1090-2651

Svazek periodika

289

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

—

Kód UT WoS článku

000914897100007

EID výsledku v databázi Scopus

2-s2.0-85134208657