Simple restriction in context-free rewriting

DOI10.1016/J.JCSS.2010.04.001MaRDI QIDQ1959430zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust

Publication date 7 October 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2010.04.001

zbMATH Keywords

context-free grammarderivation restrictionformal languagesgenerative powerrewriting system

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On restricted context-free grammars
• On context-free rewriting with a simple restriction and its computational completeness
• scientific article; zbMATH DE number 2150284
• scientific article; zbMATH DE number 3940749
• Regularity and context-freeness over word rewriting systems

Cites work

• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• A pumping lemma for random permitting context languages
• A shrinking lemma for random forbidding context languages
• A variant of random context grammars: Semi-conditional grammars
• Accepting grammars with regulation
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 709441 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On context-free rewriting with a simple restriction and its computational completeness
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Scattered context grammars
• Some restrictive devices for context-free grammars

Cited in

(7)

• scientific article; zbMATH DE number 3850487 (Why is no real title available?)
• On context-free rewriting with a simple restriction and its computational completeness
• scientific article; zbMATH DE number 4041297 (Why is no real title available?)
• On restricted context-free grammars
• A pumping lemma for permitting semi-conditional languages
• Improved descriptional complexity results on generalized forbidding grammars
• Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)

This page was built for publication: Simple restriction in context-free rewriting

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