On the degree of scattered context-sensitivity.

DOI10.1016/S0304-3975(02)00539-XzbMath1044.68077MaRDI QIDQ1401221

Henning Fernau, Alexander Meduna

Publication date: 17 August 2003

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

zbMATH Keywords

Descriptional complexityScattered context grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (6)

Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Canonical scattered context generators of sentences with their parses ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ Nonterminal complexity of tree controlled grammars ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity ⋮ A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

Cites Work

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On the degree of scattered context-sensitivity.