In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equivalent to finite automata, namely they characterize regular languages. This result has been improved in different directions, by obtaining optimal lower bounds for the time that one-tape deterministic and nondeterministic Turing machines need to recognize nonregular languages. On the other hand, in 1964 Kuroda showed that one-tape Turing machines that are not allowed to use any extra space, besides the part of the tape which initially contains the input, namely linear bounded automata, recognize exactly contextsensitive languages. In 1967 Hibbard proved that for each integer d ≥ 2, one-tape Turing machines that are allowed to rewrite each tape cell only in the first d visits are equivalent to pushdown automata. This gives a characterization of the class of context-free languages in terms of restricted Turing machines. We discuss these and other related models, by presenting an overview of some fundamental results related to them. Descriptional complexity aspects are also considered.
Restricted Turing machines and language recognition / G. Pighizzini - In: Language and automata theory and applications / [a cura di] A.-H. Dediu, J. Janoušek, C. Martín-Vide, B. Truthe. - [s.l] : Springer Verlag, 2016. - ISBN 9783319299990. - pp. 42-56 (( Intervento presentato al 10. convegno LATA tenutosi a Prague nel 2016.
Restricted Turing machines and language recognition
G. Pighizzini
2016
Abstract
In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equivalent to finite automata, namely they characterize regular languages. This result has been improved in different directions, by obtaining optimal lower bounds for the time that one-tape deterministic and nondeterministic Turing machines need to recognize nonregular languages. On the other hand, in 1964 Kuroda showed that one-tape Turing machines that are not allowed to use any extra space, besides the part of the tape which initially contains the input, namely linear bounded automata, recognize exactly contextsensitive languages. In 1967 Hibbard proved that for each integer d ≥ 2, one-tape Turing machines that are allowed to rewrite each tape cell only in the first d visits are equivalent to pushdown automata. This gives a characterization of the class of context-free languages in terms of restricted Turing machines. We discuss these and other related models, by presenting an overview of some fundamental results related to them. Descriptional complexity aspects are also considered.File | Dimensione | Formato | |
---|---|---|---|
chp%3A10.1007%2F978-3-319-30000-9_3.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
240.48 kB
Formato
Adobe PDF
|
240.48 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.