Parikh's theorem: a simple and direct automaton construction

DOI10.1016/j.ipl.2011.03.019zbMath1260.68203arXiv1006.3825MaRDI 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 language; regular language; formal languages; Parikh image

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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

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