Conjunctive and Boolean grammars: the true general case of the context-free grammars
From MaRDI portal
Publication:394967
DOI10.1016/J.COSREV.2013.06.001zbMATH Open1286.68268OpenAlexW2117111784MaRDI QIDQ394967FDOQ394967
Authors: Alexander Okhotin 
Publication date: 28 January 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2013.06.001
Recommendations
- scientific article; zbMATH DE number 2040923
- Boolean grammars
- Boolean kernels of context-free languages
- Boolean grammars and gsm mappings
- Conjunctive grammars and alternating pushdown automata
- Unambiguous Boolean grammars
- A game-theoretic characterization of Boolean grammars
- A Game-Theoretic Characterization of Boolean Grammars
- scientific article; zbMATH DE number 1062935
- Mathematical Foundations of Computer Science 2005
Cites Work
- Unambiguous conjunctive grammars over a one-letter alphabet
- Equations over sets of natural numbers with addition only
- Mathematical Foundations of Computer Science 2005
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- Preservation of unambiguity and inherent ambiguity in context-free languages
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
- A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
- On the equivalence and containment problems for context-free languages
- Title not available (Why is that?)
- Operations Which Preserve Definability in Languages
- Properties of deterministic top-down grammars
- Title not available (Why is that?)
- On the translation of languages from left to right
- A further note on top-down deterministic languages
- EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
- Letter to the Editor
- On the number of nonterminals in linear conjunctive grammars
- A simple P-complete problem and its language-theoretic representations
- One-nonterminal conjunctive grammars over a unary alphabet
- On real time one-way cellular array
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Characterizations and computational complexity of systolic trellis automata
- Closure properties of cellular automata
- Locally stratified Boolean grammars
- Conjunctive grammars with restricted disjunction
- Faster integer multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On uniform circuit complexity
- Gaussian elimination is not optimal
- Deterministic context free languages
- An efficient context-free parsing algorithm
- Matrix multiplication via arithmetic progressions
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Recognition and parsing of context-free languages in time n3
- Tree adjunct grammars
- On certain formal properties of grammars
- Notes on top-down languages
- General context-free recognition in less than cubic time
- Unrestricted complementation in language equations over a one-letter alphabet
- Boolean grammars
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- On equations over sets of numbers and their limitations
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Title not available (Why is that?)
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Title not available (Why is that?)
- On the equivalence of linear conjunctive grammars and trellis automata
- Syntax-Directed Transduction
- Two Families of Languages Related to ALGOL
- Complexity of equations over sets of natural numbers
- Representing hyper-arithmetical sets by equations over sets of integers
- Language equations with complementation: expressive power
- An efficient recognizer for the Boolean closure of context-free languages
- Language equations with complementation: decision problems
- Decision problems for language equations
- An Improved Context-Free Recognizer
- Title not available (Why is that?)
- Title not available (Why is that?)
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Recursive descent parsing for Boolean grammars
- Title not available (Why is that?)
- BOOLEAN FUZZY SETS
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- A game-theoretic characterization of Boolean grammars
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- Well-founded semantics for Boolean grammars
- Unambiguous Boolean grammars
- The hardest linear conjunctive language
- A property of real-time trellis automata
- Analytic models and ambiguity of context-free languages
- Some subclasses of context-free languages in \(NC^ 1\)
- Variations of the firing squad problem and applications
- A grammatical characterization of alternating pushdown automata
- On time computability of functions in one-way cellular automata
- A characterization of exponential-time languages by alternating context- free grammars
- The inclusion problem for simple languages
- A direct algorithm for checking equivalence of LL(k) grammars
- A recognition and parsing algorithm for arbitrary conjunctive grammars.
- Conjunctive grammars and systems of language equations
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Top-down parsing of conjunctive languages
- Fast on-line integer multiplication
- LR parsing for conjunctive grammars
- On the closure properties of linear conjunctive languages.
- P-hardness of the emptiness problem for visibly pushdown languages
- Conjunctive grammars and alternating pushdown automata
- The dual of concatenation
- An 8-state minimal time solution to the firing squad synchronization problem
- Alternating context-free languages and linear time \(\mu \)-calculus with sequential composition
- Defining contexts in context-free grammars
- Language equations with symmetric difference
- Equations \(X + A = B\) and \((X + X) + C = (X - X) + D\) over sets of natural numbers
- Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
- \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
- Systolic trellis automata: Stability, decidability and complexity
- Boolean grammars and gsm mappings
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- State complexity of operations on input-driven pushdown automata
- Homomorphisms Preserving Deterministic Context-Free Languages
- On the number of nonterminal symbols in unambiguous conjunctive grammars
- Title not available (Why is that?)
- Note on the boolean properties of context free languages
- Commutative grammars: The complexity of uniform word problems
- Title not available (Why is that?)
- On the Computational Completeness of Equations over Sets of Natural Numbers
- On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet
- Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
- Systolic trellis automatata †
- Relational queries computable in polynomial time
- One-way bounded cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Title not available (Why is that?)
- On the expressive power of univariate equations over sets of natural numbers
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Hardest Context-Free Language
- Title not available (Why is that?)
- Title not available (Why is that?)
- The equivalence problem for deterministic finite-turn pushdown automata
- Title not available (Why is that?)
- Homomorphisms preserving linear conjunctive languages
Cited In (37)
- Improved normal form for grammars with one-sided contexts
- Two-sided context specifications in formal grammars
- Well-founded semantics for Boolean grammars
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Unambiguous Boolean grammars
- Generalized LR parsing for grammars with contexts
- Rational index of languages defined by grammars with bounded dimension of parse trees
- A recognition and parsing algorithm for arbitrary conjunctive grammars.
- A tale of conjunctive grammars
- Edit distance neighbourhoods of input-driven pushdown automata
- An extension of context-free grammars with one-sided context specifications
- Hardest languages for conjunctive and Boolean grammars
- Title not available (Why is that?)
- Defining contexts in context-free grammars
- Equations over sets of integers with addition only
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Path querying with conjunctive grammars by matrix multiplication
- The multiplicative-additive Lambek calculus with subexponential and bracket modalities
- Proving language inclusion and equivalence by coinduction
- Ternary Equational Languages
- Boolean grammars
- A computation model with automatic functions and relations as primitive operations
- Language equations
- Input-driven languages are linear conjunctive
- Title not available (Why is that?)
- Formal languages over GF(2)
- Linear grammars with one-sided contexts and their automaton representation
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Linear-space recognition for grammars with contexts
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
- The hardest language for conjunctive grammars
- Inductive definitions in logic versus programs of real-time cellular automata
- Parsing by matrix multiplication generalized to Boolean grammars
- Title not available (Why is that?)
- Least and greatest solutions of equations over sets of integers
- Underlying principles and recurring ideas of formal grammars
- Generalized LR parsing algorithm for grammars with one-sided contexts
Uses Software
This page was built for publication: Conjunctive and Boolean grammars: the true general case of the context-free grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394967)
