A variant of random context grammars: Semi-conditional grammars

DOI10.1016/0304-3975(85)90056-8zbMath0587.68071OpenAlexW2107399756MaRDI QIDQ1072714

Gheorghe Păun

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

zbMATH Keywords

Chomsky hierarchycontext-sensitive languagesgenerative powercontext-free semi-conditional grammarsinclusions between families of languagesregulated derivations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (23)

Parsimonious computational completeness ⋮ Descriptional complexity of semi-conditional grammars ⋮ Generalized forbidding grammars ⋮ Accepting grammars with regulation ⋮ Single semi-contextual insertion-deletion systems ⋮ On grammars with local and global context conditions ⋮ On restricted context-free grammars ⋮ Reaction automata ⋮ Simple restriction in context-free rewriting ⋮ A Pumping Lemma for Permitting Semi-Conditional Languages ⋮ On the power of cooperation: A regular representation of recursively enumerable languages ⋮ Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ On the computational completeness of generalized forbidding matrix grammars ⋮ A note on the descriptional complexity of semi-conditional grammars ⋮ A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions ⋮ Dynamically controlled cooperating/distributed grammar systems ⋮ On context-free rewriting with a simple restriction and its computational completeness ⋮ Generalized forbidding matrix grammars and their membrane computing perspective ⋮ One-sided random context grammars ⋮ On the computational completeness of matrix simple semi-conditional grammars ⋮ Fuzzy state grammar and fuzzy deep pushdown automaton

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

This page was built for publication: A variant of random context grammars: Semi-conditional grammars