A variant of random context grammars: Semi-conditional grammars
From MaRDI portal
Publication:1072714
DOI10.1016/0304-3975(85)90056-8zbMath0587.68071MaRDI QIDQ1072714
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90056-8
Chomsky hierarchy; context-sensitive languages; generative power; context-free semi-conditional grammars; inclusions between families of languages; regulated derivations
68Q45: Formal languages and automata
Related Items
On grammars with local and global context conditions, Accepting grammars with regulation, Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars, Fuzzy state grammar and fuzzy deep pushdown automaton, A Pumping Lemma for Permitting Semi-Conditional Languages, Single semi-contextual insertion-deletion systems, On restricted context-free grammars, Reaction automata, One-sided random context grammars, Parsimonious computational completeness, A note on the descriptional complexity of semi-conditional grammars, On the power of cooperation: A regular representation of recursively enumerable languages, On the descriptional complexity of some rewriting mechanisms regulated by context conditions, Dynamically controlled cooperating/distributed grammar systems, Simple restriction in context-free rewriting, On the computing powers of \(\mathcal{L}\)-reductions of insertion languages, Generalized forbidding matrix grammars and their membrane computing perspective, On the computational completeness of matrix simple semi-conditional grammars, Descriptional complexity of semi-conditional grammars, Generalized forbidding grammars, A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions, On context-free rewriting with a simple restriction and its computational completeness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the generative capacity of tree controlled grammars
- A note on leftmost restricted random context grammars
- On the generative capacity of conditional grammars
- Grammars with partial ordering of the rules
- Programmed Grammars and Classes of Formal Languages
- Some restrictive devices for context-free grammars
