Standard

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 journalArticlepeer-review

Harvard

Okhotin, AS 2003, 'On the complexity of the string generation problem', Discrete Mathematics and Applications, vol. 13, no. 5, pp. 467-482. https://doi.org/10.1163/156939203322694745

APA

Vancouver

Okhotin AS. On the complexity of the string generation problem. Discrete Mathematics and Applications. 2003 Dec 1;13(5):467-482. https://doi.org/10.1163/156939203322694745

Author

Okhotin, A. S. / On the complexity of the string generation problem. In: Discrete Mathematics and Applications. 2003 ; Vol. 13, No. 5. pp. 467-482.

BibTeX

@article{ec38bd81912c4f4b94144e70a996b0d2,
title = "On the complexity of the string generation problem",
abstract = "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.",
author = "Okhotin, {A. S.}",
year = "2003",
month = dec,
day = "1",
doi = "10.1163/156939203322694745",
language = "English",
volume = "13",
pages = "467--482",
journal = "Discrete Mathematics and Applications",
issn = "0924-9265",
publisher = "De Gruyter",
number = "5",

}

RIS

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