scientific article; zbMATH DE number 1747449
From MaRDI portal
Publication:4531380
zbMath1004.68082MaRDI QIDQ4531380
Publication date: 1 December 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (70)
On the closure properties of linear conjunctive languages. ⋮ Computing the Shortest String and the Edit-Distance for Parsing Expression Languages ⋮ The hardest \(\operatorname{LL}(k)\) language ⋮ Boolean grammars ⋮ Equations over sets of integers with addition only ⋮ Alternating two-way AC-tree automata ⋮ Well-founded semantics for Boolean grammars ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Input-driven languages are linear conjunctive ⋮ On the complexity of the string generation problem ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ Recursive descent parsing for Boolean grammars ⋮ Generalized LR Parsing for Grammars with Contexts ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ Expressiveness and complexity of graph logic ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Generalized LR parsing algorithm for grammars with one-sided contexts ⋮ 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 language for grammars with context operators ⋮ Non-closure under complementation for unambiguous linear grammars ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Distributional learning of conjunctive grammars and contextual binary feature grammars ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ The Hardest LL(k) Language ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ A game-theoretic characterization of Boolean grammars ⋮ Complexity of equations over sets of natural numbers ⋮ Linear-space recognition for grammars with contexts ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ Path querying with conjunctive grammars by matrix multiplication ⋮ On Alternating Phrase-Structure Grammars ⋮ Distributional learning of parallel multiple context-free grammars ⋮ On hardest languages for one-dimensional cellular automata ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata ⋮ Locally stratified Boolean grammars ⋮ Unambiguous Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ The Hardest Language for Conjunctive Grammars ⋮ Decision problems for language equations ⋮ Conjunctive grammars with restricted disjunction ⋮ On state-alternating context-free grammars ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Model checking propositional dynamic logic with all extras ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Conjunctive Grammars with Restricted Disjunction ⋮ On hardest languages for one-dimensional cellular automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Path querying on acyclic graphs using Boolean grammars ⋮ Learning Conjunctive Grammars and Contextual Binary Feature Grammars ⋮ Least and greatest solutions of equations over sets of integers ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ The hardest linear conjunctive language ⋮ A Game-Theoretic Characterization of Boolean Grammars ⋮ On Equations over Sets of Numbers and Their Limitations ⋮ One-Nonterminal Conjunctive Grammars over a Unary Alphabet ⋮ Language equations with complementation: expressive power ⋮ Language equations ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ The dual of concatenation ⋮ Improved normal form for grammars with one-sided contexts ⋮ Two-sided context specifications in formal grammars ⋮ Unresolved systems of language equations: expressive power and decision problems
This page was built for publication:
