Scattered context grammars with one non-context-free production are computationally complete

DOI10.3233/FI-2021-2028MaRDI QIDQ5164863zbMATH OpenOpenAlexFDO

Authors Zbyněk Křivka, Alexander Meduna

Publication date 15 November 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2021-2028

zbMATH Keywords

computational completenessdescriptional complexityscattered context grammarssize reductionparallel productionsthe number of non-context-free productions

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• On the descriptional complexity of scattered context grammars
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• 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

Cites work

• scientific article; zbMATH DE number 1330031 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• Generative power of three-nonterminal scattered context grammars
• On the descriptional complexity of scattered context grammars
• On the generative power of regular pattern grammars
• Regulated grammars and automata
• Regulated pushdown automata
• Scattered context grammars
• Scattered context grammars and their applications.
• Scattered context grammars generate any recursively enumerable language with two nonterminals

Cited in

(10)

• Derivation in scattered context grammar via lazy function evaluation
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• On the descriptional complexity of scattered context grammars
• Coincidental extension of scattered context languages
• Homogeneous grammars with a reduced number of non-context-free products
• An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
• Jumping scattered context grammars
• Conclusive tree-controlled grammars
• CD grammar systems with two propagating scattered context components characterize the family of context sensitive languages
• Terminating left-hand sides of scattered context productions M. Nivat

This page was built for publication: Scattered context grammars with one non-context-free production are computationally complete

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