One-nonterminal conjunctive grammars over a unary alphabet

DOI10.1007/s00224-011-9319-6zbMath1248.68304OpenAlexW1997037354MaRDI QIDQ639852

Artur Jeż, Alexander Okhotin

Publication date: 11 October 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9319-6

zbMATH Keywords

decision problemslanguage equationsunary languagesconjunctive grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (8)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ The complexity of compressed membership problems for finite automata ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Language equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the expressive power of univariate equations over sets of natural numbers
• On the number of nonterminals in linear conjunctive grammars
• Complexity of equations over sets of natural numbers
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Conjunctive grammars and systems of language equations
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• Recursive descent parsing for Boolean grammars
• Commutative grammars: The complexity of uniform word problems
• On the Computational Completeness of Equations over Sets of Natural Numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• On Language Equations XXK = XXL and XM = N over a Unary Alphabet
• Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
• Word Problems and Membership Problems on Compressed Words
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS

This page was built for publication: One-nonterminal conjunctive grammars over a unary alphabet