Unambiguous Boolean grammars

DOI10.1016/j.ic.2008.03.023zbMath1328.68106OpenAlexW2039297197MaRDI QIDQ948095

Alexander Okhotin

Publication date: 8 October 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.023

zbMATH Keywords

ambiguityparsingBoolean grammarsconjunctive grammars

Mathematics Subject Classification ID

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

Related Items (12)

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages ⋮ Input-driven languages are linear conjunctive ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Linear-space recognition for grammars with contexts ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Conjunctive grammars with restricted disjunction ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Conjunctive Grammars with Restricted Disjunction ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• Characterizations and computational complexity of systolic trellis automata
• The hardest linear conjunctive language
• Parallel time O(log n) recognition of unambiguous context-free languages
• A very hard log-space counting class
• Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
• Boolean grammars
• Sublogarithmic ambiguity
• Recursive descent parsing for Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Well-Founded Semantics for Boolean Grammars
• Systolic trellis automatata †
• On the equivalence of linear conjunctive grammars and trellis automata
• Expressive Power of LL(k) Boolean Grammars
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• Ambiguity in context free languages
• A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
• A helpful result for proving inherent ambiguity
• An efficient context-free parsing algorithm
• Two Families of Languages Related to ALGOL
• The undecidability of the ambiguity problem for minimal linear grammars

This page was built for publication: Unambiguous Boolean grammars