Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars

DOI10.3233/FI-2021-2056OpenAlexW3191309876MaRDI QIDQ5158664

Henning Fernau, Rufus O. Oladele, Indhumathi Raman, Lakshmanan Kuppusamy

Publication date: 25 October 2021

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

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

zbMATH Keywords

computational completenesssimple semi-conditional grammarsdescriptional complexity measuresGeffert normal forms

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the descriptional complexity of semi-conditional grammars
• A variant of random context grammars: Semi-conditional grammars
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• New nonterminal complexity results for semi-conditional grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Descriptional complexity of semi-conditional grammars
• On the power of permitting semi-conditional grammars
• On certain formal properties of grammars
• A note on phrase structure grammars
• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• Normal forms for phrase-structure grammars
• Two Families of Languages Related to ALGOL
• Some restrictive devices for context-free grammars
• Improved descriptional complexity results on generalized forbidding grammars

This page was built for publication: Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars