Limited Automata: Properties, Complexity and Variants - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Limited Automata: Properties, Complexity and Variants

Giovanni Pighizzini

Résumé

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.
Fichier principal
Vignette du fichier
480958_1_En_4_Chapter.pdf (371.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02387288 , version 1 (29-11-2019)

Licence

Paternité

Identifiants

Citer

Giovanni Pighizzini. Limited Automata: Properties, Complexity and Variants. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.57-73, ⟨10.1007/978-3-030-23247-4_4⟩. ⟨hal-02387288⟩
32 Consultations
66 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More