On the generative capacity of tree controlled grammars

DOI10.1007/BF02253054zbMath0392.68060OpenAlexW13810807MaRDI QIDQ1251904

Gheorghe Păun

Publication date: 1979

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02253054

zbMATH Keywords

Context-FreeControl LanguageGenerative Capacity of Tree Controlled GrammarsLambda-FreeRegular Grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

On the Nonterminal Complexity of Tree Controlled Grammars ⋮ On computational complexity of contextual languages ⋮ Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Two collapsing hierarchies of subregularly tree controlled languages ⋮ Nonterminal complexity of tree controlled grammars ⋮ GENERATIVE CAPACITY OF SUBREGULARLY TREE CONTROLLED GRAMMARS ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity ⋮ On the generative capacity of tree controlled grammars ⋮ On Szilard's languages associated to a matrix grammar ⋮ Unnamed Item ⋮ A variant of random context grammars: Semi-conditional grammars

Cites Work

• Unnamed Item
• Tree controlled grammars
• On the generative capacity of tree controlled grammars
• An analog of a theorem about context-free languages
• Simple matrix languages with a leftmost restriction

This page was built for publication: On the generative capacity of tree controlled grammars