Deterministic Pushdown Automata and Unary Languages

DOI10.1007/978-3-540-70844-5_24MaRDI QIDQ3602818zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Recommendations

• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Finite automata and unary languages
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• scientific article; zbMATH DE number 1502111
• Parikh image of pushdown 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 1502111 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A pushdown automaton or a context-free grammar - which is more economical?
• A regularity test for pushdown machines
• Implementation and Application of Automata
• Mappings which preserve context sensitive languages
• On the translation of languages from left to right
• Optimal simulations between unary automata
• Regularity and Related Problems for Deterministic Pushdown Automata
• Simulating finite automata with context-free grammars.
• Tight lower bounds on the length of word chains
• Two Families of Languages Related to ALGOL
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.

Cited in

(13)

• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Deciding determinism of unary languages
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• scientific article; zbMATH DE number 1283994 (Why is no real title available?)
• Limited automata and unary languages
• scientific article; zbMATH DE number 1759446 (Why is no real title available?)
• Unary pushdown automata and straight-line programs
• scientific article; zbMATH DE number 2106352 (Why is no real title available?)
• Deterministic two-way one-head pushdown automata are very powerful
• Investigations on automata and languages over a unary alphabet
• Parikh image of pushdown automata
• Unary Languages Recognized by Two-Way One-Counter Automata
• Investigations on Automata and Languages over a Unary Alphabet

This page was built for publication: Deterministic Pushdown Automata and Unary Languages

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