A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
One-Nonterminal Conjunctive Grammars over a Unary Alphabet
Tekijät: Jez A, Okhotin A
Kustantaja: SPRINGER
Julkaisuvuosi: 2011
Journal: Theory of Computing Systems
Tietokannassa oleva lehden nimi: THEORY OF COMPUTING SYSTEMS
Lehden akronyymi: THEOR COMPUT SYST
Numero sarjassa: 2
Vuosikerta: 49
Numero: 2
Aloitussivu: 319
Lopetussivu: 342
Sivujen määrä: 24
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-011-9319-6
Tiivistelmä
Conjunctive grammars over an alphabet I ={a} pound are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X=I center dot(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.
Conjunctive grammars over an alphabet I ={a} pound are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X=I center dot(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.
Turun yliopiston Tutkimustietojärjestelmän portaali