Generative power of three-nonterminal scattered context grammars

DOI10.1016/S0304-3975(00)00153-5MaRDI QIDQ1583096zbMATH OpenFDO

Authors Alexander Meduna

Publication date 26 October 2000

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00153-5

zbMATH Keywords

scattered context grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On the descriptional complexity of scattered context grammars
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages

Cites work

• On the generative power of regular pattern grammars
• Terminating left-hand sides of scattered context productions M. Nivat

Cited in

(19)

• On the descriptional complexity of scattered context grammars
• A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
• On the degree of scattered context-sensitivity.
• Nonterminal complexity of programmed grammars.
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Syntactic complexity of scattered context grammars
• Canonical scattered context generators of sentences with their parses
• Uniform generation of languages by scattered context grammars
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Jumping scattered context grammars
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• Scattered context grammars with one non-context-free production are computationally complete
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Scattered context grammars with one non-context-free production and six nonterminals are computationally complete
• Final sentential forms
• Nonterminal complexity of tree controlled grammars

This page was built for publication: Generative power of three-nonterminal scattered context grammars

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