Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 115 - 123 DOI 10.1051/ita:2005006

Theoret. Informatics Appl. 39, 115-123 (2005)
DOI: 10.1051/ita:2005006

Similarity relations and cover automata

Jean-Marc Champarnaud¹, Franck Guingne^{1, 2} and Georges Hansel<sup>1

1</sup>  LIFAR, Université de Rouen, France; jean-marc.champarnaud@univ-rouen.fr& franck.guingne@univ-rouen.fr & georges.hansel@univ-rouen.fr
²  XRCE, Xerox, 38240 Meylan, France; franck.guingne@xrce.xerox.com

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.

Mathematics Subject Classification. 68Q25, 68Q45, 68W01, 68W10

Key words: Finite automata -- cover automaton for a finite language -- similarity relation


© EDP Sciences 2005

What is OpenURL?