Limited automata and unary languages
From MaRDI portal
Publication:5915989
DOI10.1016/j.ic.2019.01.002zbMath1427.68153OpenAlexW4205844015MaRDI QIDQ5915989
Giovanni Pighizzini, Luca Prigioniero
Publication date: 2 May 2019
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2434/522898
Related Items
Performing regular operations with 1-limited automata, Unnamed Item, Two-way machines and de Bruijn words, Once-Marking and Always-Marking 1-Limited Automata, Linear-time limited automata, Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata, Converting nondeterministic two-way automata into small deterministic linear-time machines
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional complexity of bounded context-free languages
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- An elementary proof of a generalization of double Greibach normal form
- An elementary proof of double Greibach normal form
- Descriptional complexity of limited automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet
- The Missing Case in Chomsky-Schützenberger Theorem
- Limited Automata and Context-Free Languages
- Non-erasing Variants of the Chomsky–Schützenberger Theorem
- Automatic Sequences
- Strongly Limited Automata
- LIMITED AUTOMATA AND REGULAR LANGUAGES
- On Simulation Cost of Unary Limited Automata
- Matrix Equations and Normal Forms for Context-Free Grammars
- On Context-Free Languages
- Two Families of Languages Related to ALGOL
- A generalization of context-free determinism