Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-13T06:46:50.871Z Has data issue: false hasContentIssue false
  • English
  • Français

Similarity relations and cover automata

Published online by Cambridge University Press:  15 March 2005

Jean-Marc Champarnaud ,
Franck Guingne  and
Georges Hansel
Jean-Marc Champarnaud
Affiliation:
LIFAR, Université de Rouen, France; [email protected]& [email protected] & [email protected]
Franck Guingne
Affiliation:
LIFAR, Université de Rouen, France; [email protected]& [email protected] & [email protected] XRCE, Xerox, 38240 Meylan, France; [email protected]
Georges Hansel
Affiliation:
LIFAR, Université de Rouen, France; [email protected]& [email protected] & [email protected]
Get access

Abstract

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.

Keywords

Finite automatacover automaton for a finite languagesimilarity relation
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 1: Imre Simon, the tropical computer scientist , January 2005 , pp. 115 - 123
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Câmpeanu, C., Sântean, N. and Minimal Cover-automata, S. Yu for Finite Languages. Theor. Comput. Sci. 267 (2001) 3–16. CrossRef
Câmpeanu, C., Păun, A. and An Efficient Al, S. Yugorithm for Constructing Minimal Cover Automata for Finite Languages. Int. J. Foundations Comput. Sci. 13-1 (2002) 99–113.
Dwork, C. and Stockmeyer, L., Time Complexity Gap, A for Two-Way Probabilistic Finite-State Automata. SIAM J. Comput. 19 (1990) 1011–1023. CrossRef
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation . Addison-Wesley, Reading MA (1979).
Kaneps, J. and Friedvalds, R., Running Time to Recognize Non-Regular Languages by 2-Way Probabilistic Automata, in ICALP'91. Lect. Notes Comput. Sci. 510 (1991) 174–185. CrossRef
Körner, H., Time, A and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages. Int. J. Foundations Comput. Sci. 14 (2003) 1071–1086. CrossRef
N. Sântean, Towards a Minimal Representation for Finite Languages: Theory and Practice. Master Thesis, The University of Western Ontario (2000).
S. Yu, Regular Languages, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer, Berlin (1997).