A simplified proof of Parikh's theorem
From MaRDI portal
Publication:1241068
DOI10.1016/0012-365X(77)90103-0zbMath0364.68075OpenAlexW2023594663WikidataQ127952183 ScholiaQ127952183MaRDI QIDQ1241068
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
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 ⋮ Hairpin completions and reductions: semilinearity properties ⋮ Parikh's theorem: a simple and direct automaton construction ⋮ Commutative Lambek grammars ⋮ When is context-freeness distinguishable from regularity? An extension of Parikh's theorem ⋮ A Proof of Parikh’s Theorem via Dickson’s Lemma ⋮ Modelization of deterministic rational relations
Cites Work
- A strong pumping lemma for context-free languages
- A characterization of context-free languages
- AFL with the semilinear property
- A generalization of Parikh's semilinear theorem
- Commutative Regular Equations and Parikh's Theorem
- On Context-Free Languages
- A representation theorem for algebraic and context-free power series in noncommuting variables
- A helpful result for proving inherent ambiguity
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
