BOOLEAN GRAMMARS AND GSM MAPPINGS

DOI10.1142/S0129054110007568zbMath1207.68176MaRDI QIDQ3056280

Alexander Okhotin, Tommi Lehtinen

Publication date: 11 November 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

closure propertieslanguage equationsBoolean grammarsconjunctive grammarsgsm mappings

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (6)

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 ⋮ The Hardest Language for Conjunctive Grammars ⋮ HOMOMORPHISMS PRESERVING DETERMINISTIC CONTEXT-FREE LANGUAGES

Cites Work

• Unnamed Item
• Characterizations and computational complexity of systolic trellis automata
• Well-founded semantics for Boolean grammars
• Unambiguous Boolean grammars
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Recursive descent parsing for Boolean grammars
• Systolic trellis automata: Stability, decidability and complexity
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• On the equivalence of linear conjunctive grammars and trellis automata
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• Preservation of unambiguity and inherent ambiguity in context-free languages
• The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
• Operations Which Preserve Definability in Languages

This page was built for publication: BOOLEAN GRAMMARS AND GSM MAPPINGS