caa a22 4500 378882570 CHVBK 20180305123435.0 cr unu---uuuuu 161128e20031001xx s 000 0 eng 10.1515/156939203322694745 doi (NATIONALLICENCE)gruyter-10.1515/156939203322694745 Okhotin A. S. On the complexity of the string generation problem [Elektronische Daten] [A. S. Okhotin] 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 problem as 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 lexicographically between these strings. It is proved that this problem is 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. Copyright 2003, Walter de Gruyter Discrete Mathematics and Applications Walter de Gruyter 13/5(2003-10-01), 467-482 0924-9265 13:5<467 2003 13 dma https://doi.org/10.1515/156939203322694745 text/html Onlinezugriff via DOI 1 research article jats NATIONALLICENCE 856 40 https://doi.org/10.1515/156939203322694745 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Okhotin A. S. NATIONALLICENCE 773 0- Discrete Mathematics and Applications Walter de Gruyter 13/5(2003-10-01), 467-482 0924-9265 13:5<467 2003 13 dma CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-gruyter