On the descriptional complexity of some rewriting mechanisms regulated by context conditions

DOI10.1016/j.tcs.2004.06.032zbMath1078.68067OpenAlexW2036694812MaRDI QIDQ1763724

György Vaszil

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.032

zbMATH Keywords

Descriptional complexityScattered context grammarsRegulated rewritingSimple semi-conditional grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (13)

Descriptional complexity of semi-conditional grammars ⋮ Nonterminal complexity of one-sided random context grammars ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Canonical scattered context generators of sentences with their parses ⋮ Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars ⋮ Nonterminal complexity of tree controlled grammars ⋮ A note on the descriptional complexity of semi-conditional grammars ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity ⋮ On the descriptional complexity of scattered context grammars ⋮ A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions ⋮ Scattered context grammars that erase nonterminals in a generalized \(k\)-limited way ⋮ Improved descriptional complexity results on generalized forbidding grammars ⋮ On the computational completeness of matrix simple semi-conditional grammars

Cites Work

• A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
• A variant of random context grammars: Semi-conditional grammars
• Scattered versus context-sensitive rewriting
• On the degree of scattered context-sensitivity.
• Forbidding ET0L grammars.
• Generative power of three-nonterminal scattered context grammars
• Syntactic complexity of scattered context grammars
• Scattered context grammars
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
• Grammars with partial ordering of the rules
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the descriptional complexity of some rewriting mechanisms regulated by context conditions