A proof of Parikh's theorem via Dickson's lemma

DOI10.1142/S012905412150009XMaRDI QIDQ5859679zbMATH OpenOpenAlexWikidataFDO

Authors Toshihiro Koga

Publication date 19 April 2021

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s012905412150009x

zbMATH Keywords

commutative monoidcontext-free languagesParikh's theorem

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• A Fully Equational Proof of Parikh's Theorem
• Parikh's theorem: a simple and direct automaton construction
• Generalizing Parikh's theorem
• A formal proof of Dickson's lemma in ACL2
• Formalization of the pumping lemma for context-free languages

Cites work

• A simplified proof of Parikh's theorem
• Automated Deduction – CADE-20
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Parikh's theorem: a simple and direct automaton construction
• Rational sets in commutative monoids
• Semigroups, Presburger formulas, and languages

This page was built for publication: A proof of Parikh's theorem via Dickson's lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859679)