Conjunctive grammars with restricted disjunction

DOI10.1016/J.TCS.2010.03.015MaRDI QIDQ974750zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin, Christian Reitwießner

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)

Recommendations

• Conjunctive Grammars with Restricted Disjunction
• scientific article; zbMATH DE number 1747449
• On the number of nonterminal symbols in unambiguous conjunctive grammars
• A tale of conjunctive grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES

Cites work

• scientific article; zbMATH DE number 3426894 (Why is no real title available?)
• scientific article; zbMATH DE number 176239 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Recursive descent parsing for Boolean grammars
• Two Families of Languages Related to ALGOL
• Unambiguous Boolean grammars

Cited in

(12)

• Conjunctive grammars and alternating pushdown automata
• Comparing linear conjunctive languages to subfamilies of the context-free languages
• Language equations with complementation: expressive power
• Conjunctive Grammars with Restricted Disjunction
• Language equations
• Expressive power of \(\text{LL}(k)\) Boolean grammars
• The hardest language for grammars with context operators
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• scientific article; zbMATH DE number 1755608 (Why is no real title available?)
• The hardest language for conjunctive grammars
• An extension of context-free grammars with one-sided context specifications
• Hardest languages for conjunctive and Boolean grammars

Describes a project that uses

Uses Software

• ALGOL 60

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974750)