Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
From MaRDI portal
Publication:388216
DOI10.1016/j.ic.2013.06.003zbMath1358.68172arXiv1212.1346OpenAlexW2050310895WikidataQ61677497 ScholiaQ61677497MaRDI QIDQ388216
Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki
Publication date: 19 December 2013
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.1346
finite automatoncontext-free grammardescriptional complexityParikh equivalenceParikh's theoremsemilinear set
Related Items
State complexity of permutation on finite languages over a binary alphabet ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Unnamed Item ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Limited automata and unary languages ⋮ Characterization and complexity results on jumping finite automata
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified proof of Parikh's theorem
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Parikh's theorem: a simple and direct automaton construction
- Magic numbers in the state hierarchy of finite automata
- Semigroups, Presburger formulas, and languages
- Complementing two-way finite automata
- Parikh’s Theorem and Descriptional Complexity
- A Fully Equational Proof of Parikh's Theorem
- Chrobak Normal Form Revisited, with Applications
- Automated Deduction – CADE-20
- On Context-Free Languages
- Two Families of Languages Related to ALGOL
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
