Research output: Contribution to journal › Article › peer-review
One-Nonterminal Conjunctive Grammars over a Unary Alphabet. / Jez, Artur; Okhotin, Alexander.
In: Theory of Computing Systems, Vol. 49, No. 2, 01.08.2011, p. 319-342.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 41142832