TY - JOUR

T1 - One-Nonterminal Conjunctive Grammars over a Unary Alphabet

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2011/8/1

Y1 - 2011/8/1

N2 - 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.

AB - 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.

KW - Conjunctive grammars

KW - Decision problems

KW - Language equations

KW - Unary languages

UR - http://www.scopus.com/inward/record.url?scp=78751614842&partnerID=8YFLogxK

U2 - 10.1007/s00224-011-9319-6

DO - 10.1007/s00224-011-9319-6

M3 - Article

AN - SCOPUS:78751614842

VL - 49

SP - 319

EP - 342

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -