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

bounded widthcontext-free languagesParikh's theorem

Mathematics Subject Classification ID

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

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

(12)

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

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)