Space Complexity of Stack Automata Models

DOI10.1142/s0129054121420090zbMath1518.68178arXiv2212.00891OpenAlexW3199131588MaRDI QIDQ6169902

Oscar H. Ibarra, Luca Prigioniero, Ian McQuillan, Jozef jun. Jirásek

Publication date: 15 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2212.00891

zbMATH Keywords

pushdown automataspace complexitystack automatachecking stack automatamachine models

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Tree-walking-storage automata ⋮ Visit-bounded stack automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stack languages and log n space
• On store languages of language acceptors
• The power of two-way deterministic checking stack automata
• Pushdown automata and constant height: decidability and bounds
• Checking automata and one-way stack languages
• Visibly pushdown languages
• Deterministic Stack Transducers
• Mathematical Foundations of Computer Science 2005
• Sets accepted by one-way stack automata are context sensitive
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies

This page was built for publication: Space Complexity of Stack Automata Models