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.

Converting nondeterministic two-way automata into small deterministic linear-time machines / B. Guillon, G. Pighizzini, L. Prigioniero, D. Prusa. - In: INFORMATION AND COMPUTATION. - ISSN 1090-2651. - 289:Part A(2022). [10.1016/j.ic.2022.104938]

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

G. Pighizzini
Secondo
;
L. Prigioniero
Penultimo
;
2022

Abstract

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.
Descriptional complexity; One-tape Turing machines; Sakoda-Sipser conjecture; Two-way automata
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
wrhm-part2.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 360.23 kB
Formato Adobe PDF
360.23 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/949216
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact