Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata

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

zbMATH Keywords

context-free grammarsregular languagespushdown automatadescriptional complexitylimited automatanon-self-embedding grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

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