Elementariness of a finite set of words is co-NP-complete
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) no. 5, pp. 459-470. 
@article{ITA_1990__24_5_459_0,
     author = {Neraud, Jean},
     title = {Elementariness of a finite set of words is {co-NP-complete}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {459--470},
     publisher = {EDP-Sciences},
     volume = {24},
     number = {5},
     year = {1990},
     mrnumber = {1080501},
     zbl = {0704.68065},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1990__24_5_459_0/}
}
TY  - JOUR
AU  - Neraud, Jean
TI  - Elementariness of a finite set of words is co-NP-complete
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1990
SP  - 459
EP  - 470
VL  - 24
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1990__24_5_459_0/
LA  - en
ID  - ITA_1990__24_5_459_0
ER  - 
%0 Journal Article
%A Neraud, Jean
%T Elementariness of a finite set of words is co-NP-complete
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1990
%P 459-470
%V 24
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1990__24_5_459_0/
%G en
%F ITA_1990__24_5_459_0
Neraud, Jean. Elementariness of a finite set of words is co-NP-complete. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) no. 5, pp. 459-470. http://archive.numdam.org/item/ITA_1990__24_5_459_0/

1. S. Baase, Introduction to Design and Analysis. Addison Wesley, 1982.

2. J. Berstel, and D. Perrin, Theory of codes, Academic Press, 1985. | MR | Zbl

3. J. Berstel,D. Perrin,J. F. Perrot and A. Restivo, Sur le théorème du défaut, Journal of Algebra, September 1979, 60, n° 1, pp. 169-180. | MR | Zbl

4. K. Culik Ii and I. Fris, The decidability of equivalence problem for DOL- systems, Inform. Control, 1977, 33, pp. 20-39. | MR | Zbl

5. A. Ehrenfeucht and G. Rosenberg, Elementary homomorphisms and a solution to DOL sequence equivalence problem, Theoret. Comput. Sci., 1978, 7, pp. 76-85. | MR | Zbl

6. M. Garey and D. Johnson, Computers and intractability, W. H. Freeman and Company, 1979. | MR | Zbl

7. J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computations, Addison-Wesley Publishing Company, 1979. | MR | Zbl

8. J. Karhumäki, On Recent Trends in Formal Language Theory, in the Procedings of the 14th ICALP, 1987, pp. 136-161. | MR | Zbl

9. M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Addison- Wesley, 1983. | MR | Zbl

10. G. S. Makanin, The problem of solvability of equations in a free semigroup, Math. Sb., 1977, 103, pp. 147-236 (English translation) in Math USSR Sb., 1979, 32, pp. 129-19. | MR | Zbl

11. J. P. Pécuchet, Sur la détermination du rang d'une équation dans le monoïde libre, Theoret. Comput. Sci., 1981, 16, pp. 337-340 | MR | Zbl

12. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, Academic Press, 1980. | MR | Zbl

13. J. C. Spehner, Quelques problèmes d'extension, de conjugaison et de présentation des sous-monoïdes d'un monoïde libre, Thèse, Université Paris-VII (France), 1976.

14. L. Valiant, The equivalence problem for DOL Systems, in the Proceedings of the 3rd ICALP, 1976, pp. 31-37. | Zbl