Conjunctive and Boolean grammars: the true general case of the context-free grammars
From MaRDI portal
(Redirected from Publication:394967)
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
- scientific article; zbMATH DE number 3426894 (Why is no real title available?)
- scientific article; zbMATH DE number 3885334 (Why is no real title available?)
- scientific article; zbMATH DE number 3174044 (Why is no real title available?)
- scientific article; zbMATH DE number 5605108 (Why is no real title available?)
- scientific article; zbMATH DE number 3978426 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3696500 (Why is no real title available?)
- scientific article; zbMATH DE number 3470007 (Why is no real title available?)
- scientific article; zbMATH DE number 3504474 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 1346519 (Why is no real title available?)
- scientific article; zbMATH DE number 522856 (Why is no real title available?)
- scientific article; zbMATH DE number 1962782 (Why is no real title available?)
- scientific article; zbMATH DE number 1747449 (Why is no real title available?)
- scientific article; zbMATH DE number 941397 (Why is no real title available?)
- scientific article; zbMATH DE number 1408351 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3302285 (Why is no real title available?)
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
- A characterization of exponential-time languages by alternating context- free grammars
- A direct algorithm for checking equivalence of LL(k) grammars
- A further note on top-down deterministic languages
- A game-theoretic characterization of Boolean grammars
- A grammatical characterization of alternating pushdown automata
- A property of real-time trellis automata
- A recognition and parsing algorithm for arbitrary conjunctive grammars.
- A simple P-complete problem and its language-theoretic representations
- Alternating context-free languages and linear time \(\mu \)-calculus with sequential composition
- An 8-state minimal time solution to the firing squad synchronization problem
- An Improved Context-Free Recognizer
- An efficient context-free parsing algorithm
- An efficient recognizer for the Boolean closure of context-free languages
- Analytic models and ambiguity of context-free languages
- BOOLEAN FUZZY SETS
- Boolean grammars
- Boolean grammars and gsm mappings
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Characterizations and computational complexity of systolic trellis automata
- Closure properties of cellular automata
- Commutative grammars: The complexity of uniform word problems
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- Complexity of equations over sets of natural numbers
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Conjunctive grammars and alternating pushdown automata
- Conjunctive grammars and systems of language equations
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Conjunctive grammars with restricted disjunction
- Decision problems for language equations
- Defining contexts in context-free grammars
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Deterministic context free languages
- EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
- Equations \(X + A = B\) and \((X + X) + C = (X - X) + D\) over sets of natural numbers
- Equations over sets of natural numbers with addition only
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Fast on-line integer multiplication
- Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
- Faster integer multiplication
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- Gaussian elimination is not optimal
- General context-free recognition in less than cubic time
- Homomorphisms Preserving Deterministic Context-Free Languages
- Homomorphisms preserving linear conjunctive languages
- LR parsing for conjunctive grammars
- Language equations with complementation: decision problems
- Language equations with complementation: expressive power
- Language equations with symmetric difference
- Letter to the Editor
- Linear conjunctive grammars and one-turn synchronized alternating pushdown automata
- Locally stratified Boolean grammars
- Mathematical Foundations of Computer Science 2005
- Matrix multiplication via arithmetic progressions
- Note on the boolean properties of context free languages
- Notes on top-down languages
- On certain formal properties of grammars
- On equations over sets of numbers and their limitations
- On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet
- On real time one-way cellular array
- On the Computational Completeness of Equations over Sets of Natural Numbers
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- On the closure properties of linear conjunctive languages.
- On the equivalence and containment problems for context-free languages
- On the equivalence of linear conjunctive grammars and trellis automata
- On the expressive power of univariate equations over sets of natural numbers
- On the number of nonterminal symbols in unambiguous conjunctive grammars
- On the number of nonterminals in linear conjunctive grammars
- On the translation of languages from left to right
- On time computability of functions in one-way cellular automata
- On uniform circuit complexity
- One-nonterminal conjunctive grammars over a unary alphabet
- One-way bounded cellular automata
- Operations Which Preserve Definability in Languages
- P-hardness of the emptiness problem for visibly pushdown languages
- Parsing Boolean grammars over a one-letter alphabet using online convolution
- Preservation of unambiguity and inherent ambiguity in context-free languages
- Properties of deterministic top-down grammars
- Recognition and parsing of context-free languages in time n3
- Recursive descent parsing for Boolean grammars
- Relational queries computable in polynomial time
- Representing hyper-arithmetical sets by equations over sets of integers
- Some subclasses of context-free languages in NC^ 1
- State complexity of operations on input-driven pushdown automata
- Syntax-Directed Transduction
- Systolic trellis automata: Stability, decidability and complexity
- Systolic trellis automatata †
- The Hardest Context-Free Language
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
- The dual of concatenation
- The equivalence problem for deterministic finite-turn pushdown automata
- The hardest linear conjunctive language
- The inclusion problem for simple languages
- Top-down parsing of conjunctive languages
- Tree adjunct grammars
- Two Families of Languages Related to ALGOL
- Unambiguous Boolean grammars
- Unambiguous conjunctive grammars over a one-letter alphabet
- Unrestricted complementation in language equations over a one-letter alphabet
- Variations of the firing squad problem and applications
- Well-founded semantics for Boolean grammars
- \(L(A)=L(B)\)? decidability results from complete formal systems
- \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
Cited in
(37)- Least and greatest solutions of equations over sets of integers
- Generalized LR parsing algorithm for grammars with one-sided contexts
- 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
- A recognition and parsing algorithm for arbitrary conjunctive grammars.
- A tale of conjunctive grammars
- Rational index of languages defined by grammars with bounded dimension of parse trees
- Hardest languages for conjunctive and Boolean grammars
- An extension of context-free grammars with one-sided context specifications
- Edit distance neighbourhoods of input-driven pushdown automata
- Equations over sets of integers with addition only
- Defining contexts in context-free grammars
- scientific article; zbMATH DE number 1747449 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 2155200 (Why is no real title available?)
- Formal languages over GF(2)
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Linear-space recognition for grammars with contexts
- Linear grammars with one-sided contexts and their automaton representation
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
- Parsing by matrix multiplication generalized to Boolean grammars
- The hardest language for conjunctive grammars
- Inductive definitions in logic versus programs of real-time cellular automata
- scientific article; zbMATH DE number 2040923 (Why is no real title available?)
- Underlying principles and recurring ideas of formal grammars
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)
