Parikh's theorem: a simple and direct automaton construction

DOI10.1016/j.ipl.2011.03.019zbMath1260.68203arXiv1006.3825OpenAlexW2102924625MaRDI QIDQ1944966

Javier Esparza, Michael Luttenberger, Pierre Ganty, Stefan Kiefer

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.3825

zbMATH Keywords

context-free languageregular languageformal languagesParikh image

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (15)

Parikh’s Theorem and Descriptional Complexity ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Convergence of Newton's method over commutative semirings ⋮ When is context-freeness distinguishable from regularity? An extension of Parikh's theorem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounded underapproximations ⋮ Verifying quantitative temporal properties of procedural programs ⋮ Further closure properties of input-driven pushdown automata ⋮ Synchronizing Automata over Nested Words ⋮ The Parikh Property for Weighted Context-Free Grammars ⋮ A Proof of Parikh’s Theorem via Dickson’s Lemma ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simplified proof of Parikh's theorem
• A generalization of Parikh's semilinear theorem
• Newtonian program analysis
• Commutative Regular Equations and Parikh's Theorem
• A Fully Equational Proof of Parikh's Theorem
• Automated Deduction – CADE-20
• Complexity of pattern-based verification for multithreaded programs
• On Context-Free Languages

This page was built for publication: Parikh's theorem: a simple and direct automaton construction