Elementariness of a finite set of words is co-NP-complete

Jean Neraud

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1990)

  • Volume: 24, Issue: 5, page 459-470
  • ISSN: 0988-3754

How to cite

top

Neraud, Jean. "Elementariness of a finite set of words is co-NP-complete." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 24.5 (1990): 459-470. <http://eudml.org/doc/92369>.

@article{Neraud1990,
author = {Neraud, Jean},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {elementariness; rank of a finite set of words; NP-complete},
language = {eng},
number = {5},
pages = {459-470},
publisher = {EDP-Sciences},
title = {Elementariness of a finite set of words is co-NP-complete},
url = {http://eudml.org/doc/92369},
volume = {24},
year = {1990},
}

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
PB - EDP-Sciences
VL - 24
IS - 5
SP - 459
EP - 470
LA - eng
KW - elementariness; rank of a finite set of words; NP-complete
UR - http://eudml.org/doc/92369
ER -

References

top
  1. 1. S. BAASE, Introduction to Design and Analysis. Addison Wesley, 1982. Zbl0407.68044
  2. 2. J. BERSTEL, and D. PERRIN, Theory of codes, Academic Press, 1985. Zbl0587.68066MR797069
  3. 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. Zbl0421.20027MR549103
  4. 4. K. CULIK II and I. FRIS, The decidability of equivalence problem for DOL- systems, Inform. Control, 1977, 33, pp. 20-39. Zbl0365.68074MR449030
  5. 5. A. EHRENFEUCHT and G. ROSENBERG, Elementary homomorphisms and a solution to DOL sequence equivalence problem, Theoret. Comput. Sci., 1978, 7, pp. 76-85. Zbl0407.68085MR509015
  6. 6. M. GAREY and D. JOHNSON, Computers and intractability, W. H. Freeman and Company, 1979. Zbl0411.68039MR519066
  7. 7. J. HOPCROFT and J. ULLMAN, Introduction to automata theory, languages, and computations, Addison-Wesley Publishing Company, 1979. Zbl0426.68001MR645539
  8. 8. J. KARHUMÄKI, On Recent Trends in Formal Language Theory, in the Procedings of the 14th ICALP, 1987, pp. 136-161. Zbl0632.68070MR912705
  9. 9. M. LOTHAIRE, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Addison- Wesley, 1983. Zbl0514.20045MR675953
  10. 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. Zbl0396.20037MR470107
  11. 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 Zbl0481.20035MR642327
  12. 12. G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems, Academic Press, 1980. Zbl0508.68031MR561711
  13. 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. 14. L. VALIANT, The equivalence problem for DOL Systems, in the Proceedings of the 3rd ICALP, 1976, pp. 31-37. Zbl0362.68104

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.