Geodesic
On the complexity of the string generation problem
Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 84-99

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2003_15_4_a4,
     author = {A. S. Okhotin},
     title = {On the complexity of the string generation problem},
     journal = {Diskretnaya Matematika},
     pages = {84--99},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_4_a4/}
}
TY  - JOUR
AU  - A. S. Okhotin
TI  - On the complexity of the string generation problem
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 84
EP  - 99
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_4_a4/
LA  - ru
ID  - DM_2003_15_4_a4
ER  - 
%0 Journal Article
%A A. S. Okhotin
%T On the complexity of the string generation problem
%J Diskretnaya Matematika
%D 2003
%P 84-99
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_4_a4/
%G ru
%F DM_2003_15_4_a4
A. S. Okhotin. On the complexity of the string generation problem. Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 84-99. http://geodesic.mathdoc.fr/item/DM_2003_15_4_a4/