A note on the descriptional complexity of semi-conditional grammars

DOI10.1016/J.IPL.2009.10.002MaRDI QIDQ990095zbMATH OpenOpenAlexFDO

Authors Fumiya Okubo

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.10.002

zbMATH Keywords

descriptional complexityformal languagessemi-conditional grammarssimple semi-conditional grammars

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 709441 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (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 variant of random context grammars: Semi-conditional grammars
• Descriptional complexity of semi-conditional grammars
• Grammars with Context Conditions and Their Applications
• Normal forms for phrase-structure grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions

Cited in

(6)

• On the computational completeness of matrix simple semi-conditional grammars
• Counting simple rules in semi-conditional grammars is not simple
• Nonterminal complexity of one-sided random context grammars
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Improved descriptional complexity results on generalized forbidding grammars
• Non-simple rule counting in semi-conditional grammars

This page was built for publication: A note on the descriptional complexity of semi-conditional grammars

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