Research output: Contribution to journal › Article › peer-review
On the complexity of the string generation problem. / Okhotin, A. S.
In: Discrete Mathematics and Applications, Vol. 13, No. 5, 01.12.2003, p. 467-482.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - On the complexity of the string generation problem
AU - Okhotin, A. S.
PY - 2003/12/1
Y1 - 2003/12/1
N2 - We consider the problem of generating strings that belong to certain languages and satisfy some additional restrictions. Languages are defined by formal grammars and automata. The following formulation of this problemas a decision one is proposed: for a language represented by a formal grammar or an automaton and a pair of strings, determine whether there exists a string in this language that lies lexicographicallybetween these strings. It is proved that this problemis NLOGSPACE-complete for deterministic and nondeterministic finite automata and for linear context-free grammars; P-complete for context-free grammars of the general form; NP-complete for alternating finite automata, for conjunctive grammars and for linear conjunctive grammars; PSPACE-complete for context sensitive grammars and linear bounded automata.
AB - We consider the problem of generating strings that belong to certain languages and satisfy some additional restrictions. Languages are defined by formal grammars and automata. The following formulation of this problemas a decision one is proposed: for a language represented by a formal grammar or an automaton and a pair of strings, determine whether there exists a string in this language that lies lexicographicallybetween these strings. It is proved that this problemis NLOGSPACE-complete for deterministic and nondeterministic finite automata and for linear context-free grammars; P-complete for context-free grammars of the general form; NP-complete for alternating finite automata, for conjunctive grammars and for linear conjunctive grammars; PSPACE-complete for context sensitive grammars and linear bounded automata.
UR - http://www.scopus.com/inward/record.url?scp=0348234760&partnerID=8YFLogxK
U2 - 10.1163/156939203322694745
DO - 10.1163/156939203322694745
M3 - Article
AN - SCOPUS:0348234760
VL - 13
SP - 467
EP - 482
JO - Discrete Mathematics and Applications
JF - Discrete Mathematics and Applications
SN - 0924-9265
IS - 5
ER -
ID: 41144851