Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
From MaRDI portal
Publication:5859666
DOI10.1142/S0129054120420071zbMath1462.68104OpenAlexW4231088732MaRDI QIDQ5859666
Luca Prigioniero, Giovanni Pighizzini, Bruno Guillon
Publication date: 19 April 2021
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054120420071
context-free grammarsregular languagespushdown automatadescriptional complexitylimited automatanon-self-embedding grammars
Related Items (2)
Pushdown automata and constant height: decidability and bounds ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Size complexity of rotating and sweeping automata
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Complexity of normal form grammars
- More concise representation of regular languages by automata and regular expressions
- Descriptional complexity of limited automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Removing nondeterminism in constant height pushdown automata
- On certain formal properties of grammars
- A note on phrase structure grammars
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- An “Interchange Lemma” for Context-Free Languages
- LIMITED AUTOMATA AND REGULAR LANGUAGES
- Nondeterminism and the size of two way finite automata
- On Simulation Cost of Unary Limited Automata
- A generalization of context-free determinism
- Limited automata and unary languages
This page was built for publication: Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata