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/

[1] Harrison M. A., Introduction to formal language theory, Reading, Mass, Addison–Wesley, 1978 | MR | Zbl

[2] Jiang T, Ravikumar B., “A note on the space complexity of some decision problems for finite automata”, Inform. Process. Lett., 40 (1991), 25–31 | DOI | MR | Zbl

[3] Jones N., “Space-bounded reducibility among combinatorial problems”, J. Comp. System Sci., 11 (1975), 68–85 | MR | Zbl

[4] Okhotin A. S., “O rasshirenii formalizma kontekstno-svobodnykh grammatik operatsiei peresecheniya”, Trudy IV Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem”, 2000, 106–109

[5] Okhotin A., “Conjunctive grammars”, J. Automata, Languages and Combinatorics, 4 (2001), 519–535 | MR | Zbl

[6] Okhotin A. S., “O $P$-polnote zadachi prinadlezhnosti dlya kon'yunktivnykh grammatik”, Diskretnaya matematika i matematicheskaya kibernetika. Trudy mezhdunarodnoi shkoly-seminara, Ratmino, 2001 | Zbl

[7] Okhotin A. S., “Kon'yunktivnye grammatiki i sistemy yazykovykh uravnenii”, Programmirovanie, 28:5 (2002), 243–249 | MR | Zbl

[8] Okhotin A., “A recognition and parsing algorithm for arbitrary conjunctive grammars”, Theoretical Computer Sci., 302 (2003), 365–399 | DOI | MR | Zbl

[9] Sudborough I. H., “A note on tape-bounded complexity classes and linear context-free languages”, J. ACM, 22 (1975), 499–500 | DOI | MR | Zbl

[10] Vollmer H., Introduction to circuit complexity, Springer, Berlin, 1999 | MR

[11] Yu S., “Regular languages”, Handbook of formal languages, 1, Springer, Berlin, 1997 | MR