Elementariness of a finite set of words is co-NP-complete
Neraud, Jean
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 459-470 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1990-01-01
@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},
     volume = {24},
     year = {1990},
     pages = {459-470},
     mrnumber = {1080501},
     zbl = {0704.68065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 459-470. http://gdmltest.u-ga.fr/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