A simplified proof of Parikh's theorem

DOI10.1016/0012-365X(77)90103-0MaRDI QIDQ1241068zbMATH OpenOpenAlexWikidataFDO

Authors Jonathan Goldstine

Publication date 1978

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(77)90103-0

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 3466545 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A characterization of context-free languages
• A generalization of Parikh's semilinear theorem
• A helpful result for proving inherent ambiguity
• A representation theorem for algebraic and context-free power series in noncommuting variables
• A strong pumping lemma for context-free languages
• AFL with the semilinear property
• Commutative Regular Equations and Parikh's Theorem
• On Context-Free Languages

Cited in

(8)

• Parikh's theorem and descriptional complexity
• Parikh's theorem: a simple and direct automaton construction
• Modelization of deterministic rational relations
• A proof of Parikh's theorem via Dickson's lemma
• Hairpin completions and reductions: semilinearity properties
• Commutative Lambek grammars
• When is context-freeness distinguishable from regularity? An extension of Parikh's theorem
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

This page was built for publication: A simplified proof of Parikh's theorem

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