Generalizing Parikh's theorem

DOI10.1007/978-94-007-0714-6_10MaRDI QIDQ5261299zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky

Publication date 3 July 2015

Published in Games, Norms and Reasons (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-94-007-0714-6_10

zbMATH Keywords

context-free languagesbounded widthParikh's theorem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• A Fully Equational Proof of Parikh's Theorem
• Parikh's theorem: a simple and direct automaton construction
• Parikh's theorem and descriptional complexity
• Extending Parikh's theorem to weighted and probabilistic context-free grammars
• scientific article; zbMATH DE number 1286205

Cited in

(10)

• A generalization of Andô’s theorem and Parrott’s example
• scientific article; zbMATH DE number 5778056 (Why is no real title available?)
• Parikh's theorem: a simple and direct automaton construction
• A proof of Parikh's theorem via Dickson's lemma
• My writing
• Extending Parikh's theorem to weighted and probabilistic context-free grammars
• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• A Fully Equational Proof of Parikh's Theorem
• scientific article; zbMATH DE number 3965455 (Why is no real title available?)
• The geometric properties of an infinitary line and plane languages

This page was built for publication: Generalizing Parikh's theorem

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