Visit-Bounded Stack Automata
Date
2023-07-23
Authors
Jirasek, Jozef
McQuillan, Ian
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
ORCID
Type
Article
Degree Level
Abstract
An automaton is k-visit-bounded if during any computation its work tape head visits each tape cell at most k times. In this paper we consider stack automata which are k-visit-bounded for some integer k. This restriction resets the visits when popping (unlike similarly defined Turing machine restrictions) which we show allows the model to accept a proper superset of context-free languages and also a proper superset of languages of visit-bounded Turing machines. We study two variants of visit-bounded stack automata: one where only instructions that move the stack head downwards increase the number of visits of the destination cell, and another where any transition increases the number of visits. We prove that the two types of automata recognize the same languages. We then show that all languages recognized by visit-bounded stack automata are effectively semilinear, and hence are letter-equivalent to regular languages, which can be used to show other properties.
Description
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http: https://doi.org/10.1007/s00224-023-10124-0.
Keywords
stack automata, visit-bounded automata, semilinear languages, Compilers and Interpreters, Computability and Recursion Theory, Data Structures, Formal Languages and Automata Theory, Lisp, Perl
Citation
Jirásek, J., McQuillan, I. Visit-Bounded Stack Automata. Theory Comput Syst 67, 956–975 (2023). https://doi.org/10.1007/s00224-023-10124-0
Degree
Department
Program
Advisor
Committee
Part Of
item.page.relation.ispartofseries
DOI
https://doi.org/10.1007/s00224-023-10124-0