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 languagesdeterministic pushdown automatadescriptional complexityunary languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Two-way machines and de Bruijn words ⋮ Descriptional complexity of limited automata ⋮ 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 ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ On Simulation Cost of Unary Limited Automata ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and 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