One-nonterminal conjunctive grammars over a unary alphabet (Q639852)

Conjunctive grammars are extensions of context-free grammars with an explicit intersection operation, that is, these grammars are characterized by language equations where the right-hand sides may contain union, intersection, and concatenation of languages, as well as singleton constants (in contrast to equations corresponding to context-free grammars where intersection is not allowed). Here a special case is studied, the case of conjunctive grammars over a unary alphabet which use only one nonterminal symbols. These grammars are in general weaker than conjunctive grammars in arbitrary form, but it is shown, as the main result of the paper, that they can represent a certain encoding of any unary conjunctive language. Next, the complexity of the so-called compressed membership problem is studied. In the unary case, the question is to determine whether a string, which is given by the binary notation of its length, belongs to the language generated by a given grammar. This problem is known to be NP-complete for context-free grammars and EXPTIME-complete for conjunctive grammars. As a consequence of the previous result it can be seen that for conjunctive grammars over a unary alphabet, the problem has the same complexity for a unique nonterminal as for an unbounded number of nonterminals. The situation is different for context-free grammars, as it is also shown here by presenting a nondeterministic logarithmic-space algorithm solving the compressed membership problem for one-nonterminal context-free grammars. On the other hand, the fully compressed version of the membership problem, where not only the string but also the description of the grammar is compressed, is NP-complete for one-nonterminal context-free grammars over unary alphabets. In the final section of the paper, some decision problems concerning one-nonterminal conjunctive grammars over unary alphabets are considered, all of which are undecidable in the multiple-nonterminal case. For one-nonterminal grammars, equivalence to a regular language is decidable, while the general equivalence problem, the finiteness, and the co-finiteness problems are shown to be \(\Pi_1\)-complete, \(\Sigma_1\)-complete, and \(\Sigma_1\)-complete, respectively.