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
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
Cites Work
- Faster Integer Multiplication
- 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
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- 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
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Recursive descent parsing for Boolean grammars
- 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
- Note on the boolean properties of context free languages
- Commutative grammars: The complexity of uniform word problems
- 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
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- On the expressive power of univariate equations over sets of natural numbers
- The Hardest Context-Free Language
- The equivalence problem for deterministic finite-turn pushdown automata
- Unambiguous Conjunctive Grammars over a One-Letter Alphabet
- 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
- Operations Which Preserve Definability in Languages
- Properties of deterministic top-down grammars
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- Improved normal form for grammars with one-sided contexts
- Two-sided context specifications in formal grammars
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Rational index of languages defined by grammars with bounded dimension of parse trees
- 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
- 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
- Generalized LR Parsing for Grammars with Contexts
- Proving language inclusion and equivalence by coinduction
- Ternary Equational Languages
- Boolean grammars
- The Hardest Language for Conjunctive Grammars
- A computation model with automatic functions and relations as primitive operations
- Language equations
- Input-driven languages are linear conjunctive
- 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
- Inductive definitions in logic versus programs of real-time cellular automata
- Parsing by matrix multiplication generalized to Boolean grammars
- Least and greatest solutions of equations over sets of integers
- Generalized LR parsing algorithm for grammars with one-sided contexts
Uses Software
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Boolean grammars 👍 👎
- A game-theoretic characterization of Boolean grammars 👍 👎
- Unambiguous Boolean grammars 👍 👎
- Boolean kernels of context-free languages 👍 👎
- Conjunctive grammars and alternating pushdown automata 👍 👎
- BOOLEAN GRAMMARS AND GSM MAPPINGS 👍 👎
- A Game-Theoretic Characterization of Boolean Grammars 👍 👎
- Mathematical Foundations of Computer Science 2005 👍 👎
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)
