Similarity relations and cover automata
Champarnaud, Jean-Marc ; Guingne, Franck ; Hansel, Georges
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 115-123 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate consequences.

Publié le : 2005-01-01
DOI : https://doi.org/10.1051/ita:2005006
Classification:  68Q25,  68Q45,  68W01,  68W10 
@article{ITA_2005__39_1_115_0,
     author = {Champarnaud, Jean-Marc and Guingne, Franck and Hansel, Georges},
     title = {Similarity relations and cover automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {39},
     year = {2005},
     pages = {115-123},
     doi = {10.1051/ita:2005006},
     mrnumber = {2132581},
     zbl = {1102.68057},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2005__39_1_115_0}
}

Champarnaud, Jean-Marc; Guingne, Franck; Hansel, Georges. Similarity relations and cover automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) pp. 115-123. doi : 10.1051/ita:2005006. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_115_0/

[1] C. Câmpeanu, N. Sântean and S. Yu, Minimal Cover-automata for Finite Languages. Theor. Comput. Sci. 267 (2001) 3-16. | Zbl 0984.68099

[2] C. Câmpeanu, A. Păun and S. Yu, An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages. Int. J. Foundations Comput. Sci. 13-1 (2002) 99-113. | Zbl 1066.68062

[3] C. Dwork and L. Stockmeyer, A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata. SIAM J. Comput. 19 (1990) 1011-1023. | Zbl 0711.68075

[4] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading MA (1979). | MR 645539 | Zbl 0426.68001

[5] J. Kaneps and R. Friedvalds, Running Time to Recognize Non-Regular Languages by 2-Way Probabilistic Automata, in ICALP'91. Lect. Notes Comput. Sci. 510 (1991) 174-185. | Zbl 0766.68098

[6] H. Körner, A Time and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages. Int. J. Foundations Comput. Sci. 14 (2003) 1071-1086. | Zbl 1104.68061

[7] N. Sântean, Towards a Minimal Representation for Finite Languages: Theory and Practice. Master Thesis, The University of Western Ontario (2000).

[8] S. Yu, Regular Languages, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer, Berlin (1997). | MR 1469994