Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars

DOI10.3233/FI-2021-2056MaRDI QIDQ5158664zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Descriptional complexity of semi-conditional grammars
• Descriptional complexity of matrix simple semi-conditional grammars
• New nonterminal complexity results for semi-conditional grammars
• Improved descriptional complexity results on generalized forbidding grammars
• Improved descriptional complexity results on generalized forbidding grammars
• scientific article; zbMATH DE number 1355184
• Descriptional complexity of context-free grammar forms
• On the computational completeness of matrix simple semi-conditional grammars
• scientific article; zbMATH DE number 5506908
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement

Cites work

• scientific article; zbMATH DE number 21368 (Why is no real title available?)
• scientific article; zbMATH DE number 709441 (Why is no real title available?)
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• A note on phrase structure grammars
• A note on the descriptional complexity of semi-conditional grammars
• A variant of random context grammars: Semi-conditional grammars
• Descriptional complexity of semi-conditional grammars
• Improved descriptional complexity results on generalized forbidding grammars
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• New nonterminal complexity results for semi-conditional grammars
• Normal forms for phrase-structure grammars
• On certain formal properties of grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• On the power of permitting semi-conditional grammars
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Some restrictive devices for context-free grammars
• Two Families of Languages Related to ALGOL

Cited in

(7)

• Improved descriptional complexity results on generalized forbidding grammars
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• Descriptional complexity of matrix simple 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
• Descriptional complexity of semi-conditional grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158664)