DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES

DOI10.1142/S0129054109006784zbMath1191.68400WikidataQ61677518 ScholiaQ61677518MaRDI QIDQ3395134

Giovanni Pighizzini

Publication date: 21 August 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

formal languages; deterministic pushdown automata; descriptional complexity; unary languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES, SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA, LIMITED AUTOMATA AND REGULAR LANGUAGES, On Simulation Cost of Unary Limited Automata, Investigations on Automata and Languages Over a Unary Alphabet, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, Descriptional complexity of limited automata

Cites Work

• 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
• Mappings which preserve context sensitive languages
• A regularity test for pushdown machines
• On the translation of languages from left to right