A Fully Equational Proof of Parikh's Theorem

DOI10.1051/ita:2002007zbMath1024.68070OpenAlexW2096801634MaRDI QIDQ4787831

Anna Ingólfsdóttir, Luca Aceto, Zoltán Ésik

Publication date: 20 November 2003

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_2_129_0

zbMATH Keywords

context-free languageParikh vectorcomplete axiomatizations

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semirings (16Y60) Equational classes, universal algebra in model theory (03C05)

Related Items

Parikh’s Theorem and Descriptional Complexity, Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata, Parikh's theorem: a simple and direct automaton construction, Newton’s Method for ω-Continuous Semirings, Algebraically complete semirings and Greibach normal form, Equational theories for automata

Cites Work

• Complete systems of \(\mathcal B\)-rational identities
• Equational elements in additive algebras
• Group axioms for iteration
• A completeness theorem for Kleene algebras and the algebra of regular events
• The complexity of equivalence problems for commutative grammars
• Floyd-Hoare logic in iteration theories
• Commutative Regular Equations and Parikh's Theorem
• On Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item