## Distances between languages and reflexivity of relations

#### Christian Choffrut

###### LIAFA, Université Paris 7

Tour 55--56, 2 Place Jussieu, 75251 Paris Cedex 05

#### Giovanni Pighizzini

###### Dipartimento di Scienze dell'Informazione

Università degli Studi di Milano

via Comelico 39 -- 20135 Milano, Italy

##### Abstract

In this paper, the notions of *k*--reflexivity and almost reflexivity of
binary relations over the free monoid *A** are introduced, which are
natural extensions of the
usual reflexivity. They can be defined relative to arbitrary
distances over *A**.
The problems of deciding whether or not a relation is almost reflexive and
whether or not it is *k*--reflexive for a given integer *k,* are studied. It
is shown that both problems are unsolvable in the case of deterministic
rational relations. Moreover, the latter problem remains undecidable
even when an oracle asserting that the relation is almost
reflexive is provided.
On the other hand, for the subclass of recognizable
relations, both problems are shown to be solvable: as a consequence, the distance between two
rational languages can be effectively computed.
Further decidability results concerning the
intermediate class of synchronized rational relations are proved.

**Download**

Compressed postscript

Compressed dvi