Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Limited Automata: Properties, Complexity and Variants

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387288
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, November 29, 2019 - 4:35:37 PM
Last modification on : Wednesday, December 8, 2021 - 9:22:07 AM

File

480958_1_En_4_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

19

Files downloads

12