Parikh’s Theorem and Descriptional Complexity

DOI10.1007/978-3-642-27660-6_30zbMath1302.68170OpenAlexW2048510WikidataQ61677507 ScholiaQ61677507MaRDI QIDQ2891382

Giovanni Pighizzini, Giovanna J. Lavado

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_30

zbMATH Keywords

finite automataformal languagesbounded languagescontext-free languagesdescriptional complexityParikh's theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

Uses Software

• ALGOL 60

Cites Work

• A simplified proof of Parikh's theorem
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Parikh's theorem: a simple and direct automaton construction
• Semigroups, Presburger formulas, and languages
• A Generalization of Ogden's Lemma
• A Fully Equational Proof of Parikh's Theorem
• Automated Deduction – CADE-20
• Descriptional Complexity of Bounded Context-Free Languages
• Bounded Algol-Like Languages
• On Context-Free Languages
• Two Families of Languages Related to ALGOL
• Unnamed Item
• Unnamed Item
• Unnamed Item