Conjunctive and Boolean grammars: the true general case of the context-free grammars
From MaRDI portal
Publication:394967
DOI10.1016/j.cosrev.2013.06.001zbMath1286.68268OpenAlexW2117111784MaRDI QIDQ394967
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
Related Items (25)
Equations over sets of integers with addition only ⋮ Input-driven languages are linear conjunctive ⋮ Generalized LR Parsing for Grammars with Contexts ⋮ Generalized LR parsing algorithm for grammars with one-sided contexts ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Proving language inclusion and equivalence by coinduction ⋮ Linear-space recognition for grammars with contexts ⋮ Path querying with conjunctive grammars by matrix multiplication ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ An extension of context-free grammars with one-sided context specifications ⋮ The Hardest Language for Conjunctive Grammars ⋮ Formal languages over GF(2) ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Least and greatest solutions of equations over sets of integers ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Ternary Equational Languages ⋮ Language equations ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Improved normal form for grammars with one-sided contexts ⋮ Two-sided context specifications in formal grammars
Uses Software
Cites Work
- Unambiguous Conjunctive Grammars over a One-Letter Alphabet
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- 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
- Deterministic context free languages
- Recognition and parsing of context-free languages in time n3
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
- Syntax-Directed Transduction
- A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
- On the equivalence and containment problems for context-free languages
- An efficient context-free parsing algorithm
- Notes on top-down languages
- Operations Which Preserve Definability in Languages
- Two Families of Languages Related to ALGOL
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On the expressive power of univariate equations over sets of natural numbers
- On the number of nonterminals in linear conjunctive grammars
- A simple P-complete problem and its language-theoretic representations
- A game-theoretic characterization of Boolean grammars
- Complexity of equations over sets of natural numbers
- One-nonterminal conjunctive grammars over a unary alphabet
- On real time one-way cellular array
- Representing hyper-arithmetical sets by equations over sets of integers
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Language equations with complementation: expressive power
- Characterizations and computational complexity of systolic trellis automata
- An efficient recognizer for the Boolean closure of context-free languages
- Closure properties of cellular automata
- Well-founded semantics for Boolean grammars
- Language equations with complementation: decision problems
- Matrix multiplication via arithmetic progressions
- Locally stratified Boolean grammars
- Unambiguous Boolean grammars
- Decision problems for language equations
- Conjunctive grammars with restricted disjunction
- 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
- On uniform circuit complexity
- A characterization of exponential-time languages by alternating context- free grammars
- General context-free recognition in less than cubic time
- Tree adjunct grammars
- The inclusion problem for simple languages
- A direct algorithm for checking equivalence of LL(k) grammars
- Unrestricted complementation in language equations over a one-letter alphabet
- 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.
- Boolean grammars
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- P-hardness of the emptiness problem for visibly pushdown languages
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Conjunctive grammars and alternating pushdown automata
- Gaussian elimination is not optimal
- The dual of concatenation
- Recursive descent parsing for Boolean grammars
- An 8-state minimal time solution to the firing squad synchronization problem
- Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition
- Defining Contexts in Context-Free Grammars
- 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
- ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS
- 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
- On certain formal properties of grammars
- Note on the boolean properties of context free languages
- Commutative grammars: The complexity of uniform word problems
- BOOLEAN FUZZY SETS
- On the Computational Completeness of Equations over Sets of Natural Numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Faster Integer Multiplication
- 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 †
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Relational queries computable in polynomial time
- One-way bounded cellular automata
- An Improved Context-Free Recognizer
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- The Hardest Context-Free Language
- The equivalence problem for deterministic finite-turn pushdown automata
- On the equivalence of linear conjunctive grammars and trellis automata
This page was built for publication: Conjunctive and Boolean grammars: the true general case of the context-free grammars
