Bounded number of parallel productions in scattered context grammars with three nonterminals

DOI10.3233/FI-2010-258MaRDI QIDQ4932077zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust

Publication date 1 October 2010

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2010-258

zbMATH Keywords

descriptional complexityscattered context grammarsgenerative powerparallel productions

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On the descriptional complexity of scattered context grammars
• Generative power of three-nonterminal scattered context grammars
• Scattered context grammars with one non-context-free production are computationally complete
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• Scattered context grammars generate any recursively enumerable language with two nonterminals

Cited in

(5)

• On the descriptional complexity of scattered context grammars
• Scattered context grammars with one non-context-free production are computationally complete
• Terminating left-hand sides of scattered context productions M. Nivat
• Generative power of three-nonterminal scattered context grammars
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement

This page was built for publication: Bounded number of parallel productions in scattered context grammars with three nonterminals

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