Limited automata are single-tape Turing machines with severe rewriting restrictions. They have been introduced in 1967 by Thomas Hibbard, who proved that they have the same computational power as pushdown automata. Hence, they provide an alternative characterization of the class of context-free languages in terms of recognizing devices. After that paper, these models have been almost forgotten for many years. Only recently limited automata were reconsidered in a series of papers, where several properties of them and of their variants have been investigated. In this work we present an overview of the most important results obtained in these researches. We also discuss some related models and possible lines for future investigations.
Limited Automata: Properties, Complexity and Variants / G. Pighizzini (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] M.Hospodár, G. Jirásková, S. Konstantinidis. - Prima edizione. - [s.l] : Springer, 2019. - ISBN 9783030232467. - pp. 57-73 (( Intervento presentato al 21. convegno Descriptional Complexity of Formal Systems tenutosi a Kosice nel 2019 [10.1007/978-3-030-23247-4_4].
Limited Automata: Properties, Complexity and Variants
G. Pighizzini
2019
Abstract
Limited automata are single-tape Turing machines with severe rewriting restrictions. They have been introduced in 1967 by Thomas Hibbard, who proved that they have the same computational power as pushdown automata. Hence, they provide an alternative characterization of the class of context-free languages in terms of recognizing devices. After that paper, these models have been almost forgotten for many years. Only recently limited automata were reconsidered in a series of papers, where several properties of them and of their variants have been investigated. In this work we present an overview of the most important results obtained in these researches. We also discuss some related models and possible lines for future investigations.File | Dimensione | Formato | |
---|---|---|---|
limited.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
309.56 kB
Formato
Adobe PDF
|
309.56 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.