Non-Self-Embedding Grammars and Descriptional Complexity

DOI10.3233/FI-2021-2036OpenAlexW3160260578MaRDI QIDQ5164870

Luca Prigioniero, Giovanni Pighizzini

Publication date: 15 November 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2036

zbMATH Keywords

context-free grammarsbounded languagesdescriptional complexity

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Complexity of normal form grammars
• Finite automata and unary languages
• A new algorithm for regularizing one-letter context-free grammars.
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
• Magic numbers in the state hierarchy of finite automata
• On certain formal properties of grammars
• Two Families of Languages Related to ALGOL
• Investigations on Automata and Languages Over a Unary Alphabet
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Non-Self-Embedding Grammars and Descriptional Complexity