| Issue |
RAIRO-Theor. Inf. Appl.
Volume 39, Number 1, January-March 2005
Imre Simon, the tropical computer scientist
|
|
|---|---|---|
| Page(s) | 115 - 123 | |
| DOI | https://doi.org/10.1051/ita:2005006 | |
| Published online | 15 March 2005 | |
Similarity relations and cover automata
1
LIFAR, Université de Rouen, France;
jean-marc.champarnaud@univ-rouen.fr& franck.guingne@univ-rouen.fr & georges.hansel@univ-rouen.fr
2
XRCE, Xerox, 38240 Meylan, France;
franck.guingne@xrce.xerox.com
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.
Mathematics Subject Classification: 68Q25 / 68Q45 / 68W01 / 68W10
Key words: Finite automata / cover automaton for a finite language / similarity relation
© EDP Sciences, 2005
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.