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},
     zbl = {0704.68065},
     mrnumber = {1080501},
     language = {en},
     url = {http://www.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
DA  - 1990///
SP  - 459
EP  - 470
VL  - 24
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1990__24_5_459_0/
UR  - https://zbmath.org/?q=an%3A0704.68065
UR  - https://www.ams.org/mathscinet-getitem?mr=1080501
LA  - en
ID  - ITA_1990__24_5_459_0
ER  - 
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://www.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 797069 | Zbl 0587.68066

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 549103 | Zbl 0421.20027

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

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 509015 | Zbl 0407.68085

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

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

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

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

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 470107 | Zbl 0396.20037

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 642327 | Zbl 0481.20035

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

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 0362.68104