Scattered context grammars with one non-context-free production are computationally complete
From MaRDI portal
Publication:5164863
DOI10.3233/FI-2021-2028OpenAlexW3163941704MaRDI QIDQ5164863FDOQ5164863
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
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
computational completenessdescriptional complexityscattered context grammarssize reductionparallel productionsthe number of non-context-free productions
Cites Work
- Title not available (Why is that?)
- Regulated pushdown automata
- Title not available (Why is that?)
- On the descriptional complexity of scattered context grammars
- Generative power of three-nonterminal scattered context grammars
- Scattered context grammars
- Scattered context grammars generate any recursively enumerable language with two nonterminals
- Regulated grammars and automata
- Scattered context grammars and their applications.
- On the generative power of regular pattern grammars
- Bounded number of parallel productions in scattered context grammars with three nonterminals
Cited In (10)
- Derivation in scattered context grammar via lazy function evaluation
- On the descriptional complexity of scattered context grammars
- Bounded number of parallel productions in scattered context grammars with three nonterminals
- Coincidental extension of scattered context languages
- Terminating left-hand sides of scattered context productions M. Nivat
- Jumping scattered context grammars
- An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
- CD grammar systems with two propagating scattered context components characterize the family of context sensitive languages
- Title not available (Why is that?)
- Homogeneous grammars with a reduced number of non-context-free products
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)
