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

DOI10.3233/FI-2010-258zbMATH Open1204.68114OpenAlexW1494911824MaRDI QIDQ4932077FDOQ4932077

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

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

zbMATH Keywords

descriptional complexityscattered context grammarsgenerative powerparallel productions

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cited In (5)

• On the descriptional complexity of scattered context grammars
• 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
• Scattered context grammars with one non-context-free production are computationally complete

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)