Conjunctive grammars over an alphabet Σ={a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X=φ{symbol}(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete; the same problem for the context-free grammars is decidable in NLOGSPACE, but becomes NP-complete if the grammar is compressed as well. The equivalence problem for these grammars is shown to be co-r. e.-complete, both finiteness and co-finiteness are r. e.-complete, while equivalence to a fixed unary language with a regular positional notation is decidable.

Original languageEnglish
Pages (from-to)319-342
Number of pages24
JournalTheory of Computing Systems
Volume49
Issue number2
DOIs
StatePublished - 1 Aug 2011

    Research areas

  • Conjunctive grammars, Decision problems, Language equations, Unary languages

    Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

ID: 41142832