Pushdown automata and constant height: decidability and bounds

DOI10.1007/s00236-022-00434-0OpenAlexW4288060553WikidataQ116841309 ScholiaQ116841309MaRDI QIDQ6042073

Luca Prigioniero, Giovanni Pighizzini

Publication date: 16 May 2023

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-022-00434-0

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Pushdown and one-counter automata: constant and non-constant memory usage

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two double-exponential gaps for automata with a limited pushdown
• More concise representation of regular languages by automata and regular expressions
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Removing nondeterminism in constant height pushdown automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Optimal Simulations between Unary Automata
• New Results on the Minimum Amount of Useful Space
• A note on phrase structure grammars
• On Non-Computable Functions
• A regularity test for pushdown machines
• Two Families of Languages Related to ALGOL
• Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata