On the complexity of the string generation problem
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 378882570 | ||
| 003 | CHVBK | ||
| 005 | 20180305123435.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 161128e20031001xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1515/156939203322694745 |2 doi |
| 035 | |a (NATIONALLICENCE)gruyter-10.1515/156939203322694745 | ||
| 100 | 1 | |a Okhotin |D A. S. | |
| 245 | 1 | 0 | |a On the complexity of the string generation problem |h [Elektronische Daten] |c [A. S. Okhotin] |
| 520 | 3 | |a 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. | |
| 540 | |a Copyright 2003, Walter de Gruyter | ||
| 773 | 0 | |t Discrete Mathematics and Applications |d Walter de Gruyter |g 13/5(2003-10-01), 467-482 |x 0924-9265 |q 13:5<467 |1 2003 |2 13 |o dma | |
| 856 | 4 | 0 | |u https://doi.org/10.1515/156939203322694745 |q text/html |z Onlinezugriff via DOI |
| 908 | |D 1 |a research article |2 jats | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1515/156939203322694745 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 100 |E 1- |a Okhotin |D A. S. | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Discrete Mathematics and Applications |d Walter de Gruyter |g 13/5(2003-10-01), 467-482 |x 0924-9265 |q 13:5<467 |1 2003 |2 13 |o dma | ||
| 900 | 7 | |b CC0 |u http://creativecommons.org/publicdomain/zero/1.0 |2 nationallicence | |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-gruyter | ||