Boolean grammars

DOI10.1016/j.ic.2004.03.006zbMath1073.68037OpenAlexW2912251669WikidataQ30053738 ScholiaQ30053738MaRDI QIDQ1886037

Alexander Okhotin

Publication date: 12 November 2004

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

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

zbMATH Keywords

Conjunctive grammarLanguage equationTrellis automatonParsingIntersectionComplementCellular automatonContext-free grammar

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Grammars and rewriting systems (68Q42)

Related Items (48)

The hardest \(\operatorname{LL}(k)\) language ⋮ Equations over sets of integers with addition only ⋮ Well-founded semantics for Boolean grammars ⋮ Input-driven languages are linear conjunctive ⋮ Lower bound technique for length-reducing automata ⋮ Recursive descent parsing for Boolean grammars ⋮ Ordered context-free grammars ⋮ Language equations with complementation: decision problems ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ The Hardest LL(k) Language ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ A game-theoretic characterization of Boolean grammars ⋮ Linear-space recognition for grammars with contexts ⋮ CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES ⋮ The Boolean closure of linear context-free languages ⋮ On hardest languages for one-dimensional cellular automata ⋮ Context-free grammars with lookahead ⋮ A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Locally stratified Boolean grammars ⋮ Unambiguous Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Operator precedence and the visibly pushdown property ⋮ The Hardest Language for Conjunctive Grammars ⋮ Decision problems for language equations ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ On hardest languages for one-dimensional cellular automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ Path querying on acyclic graphs using Boolean grammars ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ A Game-Theoretic Characterization of Boolean Grammars ⋮ GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS ⋮ Ternary Equational Languages ⋮ Language equations with complementation: expressive power ⋮ BOOLEAN FUZZY SETS ⋮ NOTES ON DUAL CONCATENATION ⋮ Language equations ⋮ Decidability of trajectory-based equations ⋮ The dual of concatenation ⋮ Improved normal form for grammars with one-sided contexts ⋮ Two-sided context specifications in formal grammars ⋮ Boolean kernels of context-free languages ⋮ Unresolved systems of language equations: expressive power and decision problems

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Characterizations and computational complexity of systolic trellis automata
• Matrix multiplication via arithmetic progressions
• On uniform circuit complexity
• General context-free recognition in less than cubic time
• Tree adjunct grammars
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• On the closure properties of linear conjunctive languages.
• Systolic trellis automata: Stability, decidability and complexity
• Systolic trellis automatata †
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• The equivalence of four extensions of context-free grammars
• On the equivalence of linear conjunctive grammars and trellis automata
• Recognition and parsing of context-free languages in time n3
• Indexed Grammars—An Extension of Context-Free Grammars
• Two Families of Languages Related to ALGOL
• A cubic time extensions of context-free grammars

This page was built for publication: Boolean grammars