Space complexity of stack automata models

DOI10.1007/978-3-030-48516-0_11MaRDI QIDQ5041255zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Space Complexity of Stack Automata Models
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• Generalizations of checking stack automata: characterizations and hierarchies
• Alternating Pushdown and Stack Automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• Checking automata and one-way stack languages
• Deterministic stack transducers
• Generalizations of checking stack automata: characterizations and hierarchies
• On store languages of language acceptors
• Pushdown automata and constant height: decidability and bounds
• Sets accepted by one-way stack automata are context sensitive
• Stack languages and log n space
• The power of two-way deterministic checking stack automata
• Visibly pushdown languages

Cited in

(5)

• Iterated stack automata and complexity classes
• On dynamics of automata with a stack
• Space Complexity of Stack Automata Models
• Space-time trade-offs for stack-based algorithms
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies

This page was built for publication: Space complexity of stack automata models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041255)