On the descriptional complexity of scattered context grammars

DOI10.1016/J.TCS.2008.10.017MaRDI QIDQ1001907zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust

Publication date 19 February 2009

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

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

zbMATH Keywords

descriptional complexityscattered context grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Generative power of three-nonterminal scattered context grammars
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• Scattered context grammars with one non-context-free production are computationally complete
• Bounded number of parallel productions in scattered context grammars with three nonterminals

Cites work

• Generative power of three-nonterminal scattered context grammars
• scientific article; zbMATH DE number 4064526 (Why is no real title available?)
• scientific article; zbMATH DE number 2013189 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Scattered context grammars
• Terminating left-hand sides of scattered context productions M. Nivat

Cited in

(22)

• Scattered context grammars that erase nonterminals in a generalized \(k\)-limited way
• An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
• Coincidental extension of scattered context languages
• Terminating left-hand sides of scattered context productions M. Nivat
• Generative power of three-nonterminal scattered context grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Syntactic complexity of scattered context grammars
• Nonterminal complexity of one-sided random 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
• Two power-decreasing derivation restrictions in generalized scattered context grammars
• One-sided random context grammars with a limited number of right random context rules
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• scientific article; zbMATH DE number 1354905 (Why is no real title available?)
• Jumping scattered context grammars
• Descriptional Complexity Of Generalized Forbidding Grammars
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• CD grammar systems with two propagating scattered context components characterize the family of context sensitive languages
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• Scattered context grammars with one non-context-free production are computationally complete
• Leftmost derivations of propagating scattered context grammars: a new proof

This page was built for publication: On the descriptional complexity of scattered context grammars

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