Conjunctive grammars with restricted disjunction

DOI10.1016/j.tcs.2010.03.015zbMath1203.68078OpenAlexW1990727398MaRDI QIDQ974750

Christian Reitwießner, Alexander Okhotin

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.015

zbMATH Keywords

normal formlanguage equationsconjunctive grammarssingle tree grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (10)

Conjunctive grammars and alternating pushdown automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ The hardest language for grammars with context operators ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ An extension of context-free grammars with one-sided context specifications ⋮ The Hardest Language for Conjunctive Grammars ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ Language equations with complementation: expressive power ⋮ Language equations

Uses Software

• ALGOL 60

Cites Work

• Unambiguous Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Recursive descent parsing for Boolean grammars
• On the Computational Completeness of Equations over Sets of Natural Numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Two Families of Languages Related to ALGOL
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Conjunctive grammars with restricted disjunction