Space Complexity of Stack Automata Models

DOI10.1007/978-3-030-48516-0_11OpenAlexW3030256860MaRDI QIDQ5041255

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

Publication date: 13 October 2022

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-48516-0_11

zbMATH Keywords

pushdown automataspace complexitystack automatachecking stack automatamachine models

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Generalizations of Checking Stack Automata: Characterizations and Hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stack languages and log n space
• Generalizations of checking stack automata: characterizations and hierarchies
• 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
• Sets accepted by one-way stack automata are context sensitive

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