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