Deterministic Pushdown Automata and Unary Languages

DOI10.1007/978-3-540-70844-5_24zbMATH Open1172.68524DBLPconf/wia/Pighizzini08OpenAlexW1804899877WikidataQ61677520 ScholiaQ61677520MaRDI QIDQ3602818FDOQ3602818

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (13)

• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Deciding determinism of unary languages
• Limited automata and unary languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unary pushdown automata and straight-line programs
• Title not available (Why is that?)
• 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)