Deterministic Pushdown Automata and Unary Languages

DOI10.1007/978-3-540-70844-5_24zbMath1172.68524OpenAlexW1804899877WikidataQ61677520 ScholiaQ61677520MaRDI QIDQ3602818

Giovanni Pighizzini

Publication date: 12 February 2009

Published in: Implementation and Applications of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70844-5_24

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight lower bounds on the length of word chains
• A pushdown automaton or a context-free grammar - which is more economical?
• Simulating finite automata with context-free grammars.
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Optimal Simulations between Unary Automata
• Regularity and Related Problems for Deterministic Pushdown Automata
• Implementation and Application of Automata
• Mappings which preserve context sensitive languages
• A regularity test for pushdown machines
• Two Families of Languages Related to ALGOL
• On the translation of languages from left to right