Authors: Artur Jeż Alexander Okhotin
Publish Date: 2011/03/10
Volume: 49, Issue: 2, Pages: 319-342
Abstract
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=ϕ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 onenonterminal conjunctive grammars over a is proved to be EXPTIMEcomplete the same problem for the contextfree grammars is decidable in NLOGSPACE but becomes NPcomplete if the grammar is compressed as well The equivalence problem for these grammars is shown to be corecomplete both finiteness and cofiniteness are recomplete while equivalence to a fixed unary language with a regular positional notation is decidable
Keywords: