Distances between languages and reflexivity of relations

Christian Choffrut^{1} and Giovanni Pighizzini^{2}

1 LIAFA, Université Paris 7 Tour 55–56, 2 Place Jussieu, 75251 Paris Cedex 05 (cc@litp.ibp.fr) 2 Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano via Comelico, 39 – 20135 Milano – Italy (pighizzi@dsi.unimi.it)

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.

1 Introduction

Comparing strings has been intensively studied during the past two decades, for example in connection with bibliographic search, text editing, alignments of biologic sequences etc. The problem usually consists in associating with two strings a non negative integer which reports how close they are from each other. This usually defines a distance between words, the most popular of which is certainly the one based on the maximal common subsequence, the so-called Levenshtein distance.

The basic question concerning the subsequence distance and its extension the edit distance [Kru83] asks whether or not we can design a sequential algorithm that computes the distance in time less than O(n^{2}), where n is the maximal length of the two words.

Here we tackle the problem of computing the distance between two subsets of words. We assume these subsets to be effectively given. Actually we restrict the effectiveness of the subsets to some types of finite memory device. This is a reasonable assumption since there is no hope of actually computing the distance outside this class as we easily show in this paper.

Let A be a finite alphabet and let A^{∗} be the free monoid it generates. The passage from the distance between strings to the distance between subsets X, Y ⊆ A^{∗} of strings is done in the standard way by resorting to the Hausdorff distance. In particular, whenever X and Y are rational subsets of A^{∗} and whenever we endow the free monoid with the Hamming distance, the problem can be reduced to Hashiguchi’s result on distance-automata (caveat: the term distance here refers to a different concept, weight would be more appropriate).

It is worthwhile observing that some fundamental problems can be stated in terms of distances. For example, asking whether or not the distance, whatever the distance, between two subsets is equal to 0 amounts to asking whether or not they are equal. This question is undecidable for context-free languages, so this gives a limit to our expectations and shows that we are quickly facing difficult problems.

Intuitively, asserting that two subsets X and Y have finite distance is a claim that the binary relation X × Y is “almost” reflexive with respect to the distance under consideration. Say a relation R ⊆ A^{∗} × A^{∗} is k–reflexive, for some integer k ≤ ∞, if every element x of the domain is at distance at most k from some element y of the range, with (x, y) ∈ R, and vice versa. It is almost reflexive if k < ∞. We are led to consider the more general question of asking whether or not a given relation over A^{∗} is almost reflexive. J. Johnson [Joh86] proved that reflexivity is undecidable for rational relations. In this work, we strengthen this result by showing that the problem remains undecidable even when restricted to deterministic rational relations. This result is a new contribution to the theory of rational relations and has some important consequences concerning the problems we are interested in in this paper. First of all, we cannot decide whether or not a deterministic rational relation is k–reflexive, for a given integer k, with respect to any distance. Moreover, in the case of the distances studied in this work, namely the Hamming, subword and edit distances, this problem remains undecidable even in the presence of an oracle asserting that the relation is almost reflexive. In addition, we prove that it is undecidable whether or not a deterministic rational relation is almost reflexive, i.e., whether or not k < ∞.

Subsequently, in order to identify the largest classes of relations for which the previously mentioned properties are decidable, we restrict our attention to proper subfamilies of deterministic rational relations, in particular that of synchronized rational relations [FS93] and that of recognizable relations. Recall that the class of recognizable relations is a proper subclass of that of synchronized rational relations which is itself a proper subclass of that of deterministic rational relations (assuming A and B are non empty).

We show that Hashiguchi’s above mentioned problem is very close to the problem of deciding whether or not a synchronized rational relation is almost reflexive with respect to the Hamming distance. In fact, each problem can be immediately encoded into the other. As a consequence, we prove that the smallest k ≤ ∞ such that a synchronized rational relation is k–reflexive with respect to the Hamming distance can be effectively computed.

In the case of the subword and of the edit distances, the largest class for which we show that this computation can be done effectively is that of recognizable relations. This result does not seem to be extendable to synchronized rational relations. However, we are able to prove that given an oracle asserting that a synchronized rational relation is almost reflexive, then it is decidable whether or not it is k–reflexive, for a given integer k, with respect to the subword or edit distance. These results are summarized in the following table

Is R k–reflexive?

Is R almost reflexive?

Find the smallest k s.t. R is k–reflexive

Given R almost reflexive, find the smallest k s.t. R is k–reflexive

\begin{matrix}Rec & Syn & DRat \\ S & S & U \\ S & S/? & U \\ S & S/? & U \\ S & S & U \end{matrix}

S=Solvable, U=Unsolvable

S/?=Solvable for the Hamming distance, unknown for the edit and the subword distance Rec=Recognizable relations Syn=Synchronized rational relations DRat=Deterministic rational relations

We conclude this introduction, by mentioning that in the unary case, namely in the case of relations defined over a one letter alphabet, rational relations are equivalent to Presburger formulas [GS66]. Using this fact, we have shown that in the unary case all the considered problems are solvable. For lack of space, this result is omitted in this version of the paper. For the same reason, some of the proofs have been just outlined.

2 Preliminary definitions and results

Given a finite alphabet A, let A^{∗} be the free monoid of strings (or words) over A, and let ϵ be the empty word. Given a string x ∈ A^{∗}, we denote by |x| its length and by x_{i} its i-th symbol (or letter), i = 1, …, |x|. We recall that a string z ∈ A^{∗} is a factor or subword of x if there exist two strings u, v ∈ A^{∗} such that x = uzv.

A distance over A^{∗} is a function d : A^{∗} × A^{∗} → IN ∪ {∞} which is reflexive, symmetric, and which satisfies the triangular inequality: for all x, y, z, d(x, y) ≤ d(x, z) + d(z, y) holds.

In this paper, we consider three distances over A^{∗}. Given two strings x, y ∈ A^{∗}, the Hamming distance reports the number of positions where the symbols of x differ from those of y; the subword distance is based on the longest common subword of x and y; the edit distance is defined as the minimum number of edit operations (substitution, insertion, deletion of a symbol) which transform x into y. Formally

Definition 1. Given x, y ∈ A^{∗}, the Hamming, subword, and edit distance between x and y, denoted by d_{H}(x, y), d_{s}(x, y), and d_{e}(x, y), respectively, are defined as

– d_{H}(x, y) = \{ \begin{matrix}#\{i | x_{i} ≠ y_{i}\} & if |x| = |y| \\ ∞ & otherwise; \end{matrix}

– d_{s}(x, y) = |x| + |y| − 2 max {|z| | z is a subword of both x and y};

– d_{e}(x, y) = min \{k | x|^{\underline{k}} y\}, where for w, z ∈ A^{∗}, w| z if and only if there exist u, v ∈ A^{∗}, a, b ∈ A, with a ≠ b, such that either w = uav, z = ubv (substitution), or w = uav, z = uv (deletion), or w = uv, z = ubv (insertion), and, as usual, |^{\underline{k}} denotes the k-th power of | . Every distance over A^{∗} can be extended to a distance between a string and

a language or between two languages. The distance between a string x and a language L is defined as the minimum of the distances between x and the strings belonging to L; the distance between two languages can be defined in a standard way, by resorting to the Hausdorff distance. More precisely

Definition 2. Let A be a finite alphabet and d : A^{∗} ×A^{∗} → IN∪{∞} a distance. Given a string x ∈ A^{∗} and a language L ⊆ A^{∗}, the distance d(x, L) between x and L is defined as

d(x, L) = \{ \begin{matrix}min \{d(x, y) | y ∈ L\} & if L ≠ ∅ \\ ∞ & otherwise. \end{matrix}

Given two languages L′, L′′ ⊆ A^{∗}, the distance d(L′, L′′) between L′ and L′′ is defined as

d(L′, L′′) = max {sup {d(x, L′′) | x ∈ L′}, sup {d(x, L′) | x ∈ L′′}}.

Recalling that the equivalence problem is undecidable for context–free languages, it is immediate that the distance between context–free languages is not computable. So, it is natural to restrict our attention to subclasses of context–free languages. On the other hand, the study of the distance between two languages can be generalized to the study of reflexivity properties of relations. To this aim, we now recall some basic definitions concerning binary relations over strings, in order to introduce the notion of k–reflexive relation.

Given a binary relation R ⊆ A^{∗}×B^{∗}, let Dom(R) and Ran(R) be the domain and the range of R, respectively, namely, Dom(R) = {x | ∃y s.t. (x, y) ∈ R}, and Ran(R)={y |∃x s.t. (x, y) ∈ R}, and let R^{−1} be the relation {(y, x)|(x, y) ∈ R}.

Given a language L ⊆ A^{∗}, let i_{L} = {(x, x) | x ∈ L} be the identity relation restricted to L. A relation R ⊆ A^{∗} × A^{∗} is reflexive if and only if, for any x ∈ Dom(R) ∪ Ran(R), the pair (x, x) belongs to R, namely, i_{Dom(R)∪Ran(R)} ⊆ R. We now extend the notion of reflexivity, by introducing the k–reflexivity

Definition 3. Given a distance d over A^{∗}, a relation R ⊆ A^{∗} × A^{∗}, and an integer k ∈ IN ∪ {∞}, the relation R is k–reflexive with respect to d, if and only if the following two statements are true

– ∀x ∈ Dom(R) ∃y ∈ A^{∗} s.t. (x, y) ∈ R and d(x, y) ≤ k;

– ∀y ∈ Ran(R) ∃x ∈ A^{∗} s.t. (x, y) ∈ R and d(x, y) ≤ k. The relation R is almost reflexive (with respect to d) if and only if it is k–reflexive for some k < ∞.

Note that, for any distance d, a relation is reflexive if and only if it is 0– reflexive. Furthermore, it is not difficult to observe that the distance between two languages L′ and L′′ is bounded by k if and only if the relation L′ × L′′ is k–reflexive. Hence, L′ and L′′ have finite distance if and only if the relation L′ × L′′ is almost reflexive.

We now briefly recall the definition of the main classes of relations we are interested in. For more details the reader is referred to [Eil74, Joh86, FS93].

As usual, given a monoid M, we denote by Rec(M) the family of recognizable subsets of M (i.e., all subsets of M that are the union of some equivalence classes of a congruence of finite index) and by Rat(M) the family of rational subsets of M (i.e., all the subsets that are obtained from singletons by a finite application of the operations of set union, concatenation and Kleene star). The family Rat(A^{∗} × B^{∗}) of rational relations over A^{∗} × B^{∗} can be characterized in terms of rational transducers, i.e., of two-tape automata. By considering deterministic and synchronized transducers, we define, respectively, the classes DRat(A^{∗} × B^{∗}) and Syn(A^{∗} × B^{∗}) of deterministic and synchronized rational relations over A^{∗} × B^{∗} [FS93].

The following proper inclusions are well known [RS59, Eil74, Joh86, FS93] (we assume #A × #B ≥ 2 where #A denotes the cardinality of A)

Rec(A^{∗} × B^{∗}) ⊂ Syn(A^{∗} × B^{∗}) ⊂ DRat(A^{∗} × B^{∗}) ⊂ Rat(A^{∗} × B^{∗}).

We conclude this section by recalling that a distance automaton A (actually a finite automaton with a weight function) [Has82, Has90] is an ordinary nondeterministic automaton (A, Q, δ, I, F), along with a function ω : Q×A×Q → IN∪{∞} such that, for q, p ∈ Q, a ∈ A, ω(q, a, p) = ∞ if and only if p ∉ δ(q, a).

The weight function ω can be extended to strings, by setting, for q, p ∈ Q, x, w ∈ A^{∗}, a ∈ A

– ω(q, ϵ, p) = \{ \begin{matrix}0 & if q = p \\ ∞ & otherwise; \end{matrix}

– ω(q, wa, p) = min {ω(q, w, r) + ω(r, a, p) | r ∈ Q};

– ω(x) = min {ω(q, x, p) | q ∈ I, p ∈ F }. The weight of A, denoted by ω(A), is the maximum of the weights of the strings accepted by the underlying automaton, namely ω(A) = sup {ω(x) | x ∈ L(A)}, with the convention that if A accepts the empty set, then ω(A) = ∞. The following result was proved by Hashiguchi in [Has82, Has90].

Theorem 4. Given an automaton A with a weight function ω, the weight ω(A) is computable.

3 Undecidability results

In this section, we begin the study by showing that k–reflexivity is undecidable, for deterministic rational relations. The results we state are mainly based on the following theorem, which extends to deterministic rational relations a result proved in [Joh86] for rational relations

Theorem 5. It is undecidable whether or not a deterministic rational relation R ⊆ A^{∗} × A^{∗} is reflexive, i.e., i_{Dom(R)∪Ran(R)} ⊆ R.

Proof. Given a deterministic rational relation R ⊆ A^{∗} × A^{∗}, let X = A^{∗} − Dom(R) and Y = A^{∗}−Ran(R). Then R∪(X×Y) is deterministic too. Moreover, R is reflexive if and only if the diagonal i_{A^{∗}} is contained in R ∪ (X × Y). Now, we show that the problem of deciding whether or not a deterministic rational relation contains the diagonal is undecidable.

Given an instance u_{1}, …, u_{p}, v_{1}, …, v_{p} ∈ A^{∗} of Post Correspondence Problem (PCP) such that {u_{1}, …, u_{p}} and {v_{1}, …, v_{p}} are prefix codes, consider the relation R = {(u_{i}, v_{i}) | i = 1, …, n}^{+}. It is not difficult to see that R ∈ DRat(A^{∗} × A^{∗}). Moreover, DRat(A^{∗} × A^{∗}) is closed under complementation. Hence R^{c} ∈ DRat(A^{∗} × A^{∗}). Note that R^{c} contains the diagonal i_{A^{∗}} if and only if the given instance of PCP does not have a solution. Since PCP is undecidable even for prefix codes [Ruo85], we conclude that the reflexivity is undecidable. ⊓ ⊔

As an immediate consequence of Theorem 5, we can state the following undecidability result

Corollary 6. Let d be a fixed distance over A^{∗}. It is undecidable, given a deterministic rational relation R ∈ DRat(A^{∗} × A^{∗}) and an integer k, whether or not R is k–reflexive, relative to d.

Now, in the case of the Hamming, subword and edit distance, we strengthen the result obtained in Corollary 6 in two directions. On the one hand, we show that it is undecidable whether or not a deterministic rational relation is almost reflexive (namely, we just require the existence of a finite bound k, we do not require its value). On the other hand, we show that the problem of deciding whether or not a deterministic rational relation is k–reflexive remains undecidable even when we know it is almost reflexive.

Theorem 7. It is undecidable whether or not a deterministic rational relation is almost reflexive, relative to the Hamming, the subword, and the edit distance, respectively.

Proof. (outline) Given R ∈ DRat(A^{∗} × A^{∗}), let R_{$} = {($u$, $v$) | (u, v) ∈ R}, where $ ∉ A. Of course, R_{$} and its Kleene closure R_{$}^{∗} are deterministic.

We prove that R is reflexive if and only if R_{$}^{∗} is almost reflexive, and then, by Theorem 5, we conclude that this property is undecidable. The “only if” part is trivial. To prove the converse implication, suppose that R_{$}^{∗} is k–reflexive, for an integer k < ∞. Thus, given u ∈ Dom(R) and x = ($u$)^{k+1}, there exists y ∈ (A ∪ {$})^{∗} such that (x, y) ∈ R_{$}^{∗} and d(x, y) ≤ k.

It is not difficult to see that in the case of the Hamming and the edit distances, the string y can be decomposed as the product of k +1 factors y_{0}, y_{1}, …, y_{k} such that d(x, y) = d($u$, y_{0})+d($u$, y_{1})+…+d($u$, y_{k}). This implies that y_{i} = $u$, for some i, 0 ≤ i ≤ k. Thus, ($u$, $u$) ∈ R_{$} and (u, u) ∈ R.

In the case of the subword distance, for k = 0 it is immediate to observe that (u, u) ∈ R. For k ≥ 1, we have d_{s}(x, y) = |x| + |y| − 2l_{s}(x, y) ≤ k, where l_{s}(x, y) is the length of the longest common subword of x and y. So 2l_{s}(x, y) ≥ |x| + |y| − k ≥ (|u| + 2)(k + 1) + l_{s}(x, y) − k, and then l_{s}(x, y) ≥ 2|u| + 3. Thus, $u$ should be a subword of both x and y, and, by construction, ($u$, $u$) ∈ R_{$}, (u, u) ∈ R.

Dually, if R_{$}^{∗} is k–reflexive, then v ∈ Ran(R) implies (v, v) ∈ R. ⊓ ⊔

Theorem 8. It is undecidable whether or not a k–reflexive deterministic rational relation R ∈ DRat(A^{∗} × A^{∗}) is (k − 1)–reflexive, relative to the Hamming, the subword, and the edit distance, respectively.

Proof. We prove the result by showing that given a 1–reflexive deterministic rational relation, it is undecidable whether it is reflexive too.

First, we observe that the problem of deciding whether a deterministic rational relation R is reflexive is undecidable even if ϵ ∉ Dom(R) ∪ Ran(R). Let R be a deterministic rational relation satisfying such a restriction, and let ♯ be a symbol not belonging to A. Consider the relation R^{♯} = R ∪ R_{0} ∪ R_{1} ∪ R_{2}, where R_{0} = {(u, u^{♯}) | u ∈ Dom(R)}, R_{1} = {(u^{♯}, u) | u ∈ Ran(R)}, R_{2} = {(u^{♯}, u^{♯}) | u ∈ Dom(R) ∪ Ran(R)}, and, for any u ∈ A^{∗}, i = 1, …, k, u^{♯} denotes the word ♯u_{2} … u_{|u|}.

It is not difficult to observe that R^{♯} is a 1–reflexive deterministic rational relation, with respect to the considered distances. Furthermore, R^{♯} is reflexive if and only if R is reflexive, but, by Theorem 5, this is undecidable. ⊓ ⊔

Since the relation R^{♯} used to prove Theorem 8 is almost reflexive, actually 1–reflexive, we immediately obtain

Corollary 9. Given an almost reflexive deterministic rational relation R and an integer k ∈ IN, it is undecidable whether or not R is k–reflexive, with respect to the Hamming, the subword and the edit distance, respectively.

4 k–reflexivity relative to the Hamming distance

In Section 3, we have shown that the problem of deciding whether a deterministic rational relation is k–reflexive with respect to the Hamming distance is unsolvable. Now, we prove that this problem turns out to be solvable when we restrict our attention to the class of synchronized rational relations.

Theorem 10. For any synchronized rational relation R, it is possible to compute the smallest k ≤ ∞, such that R is k–reflexive relative to the Hamming distance.

Proof. (outline) Given R ∈ Syn(A^{∗} × A^{∗}), let A = (A, A, Q, I, F, E) be a synchronized transducer accepting R. Thus, for any transition (q, x, y, p) ∈ E of A, (x, y) ∈ (A ∪ {ϵ}) × (A ∪ {ϵ}), and (x, y) ≠ (ϵ, ϵ) holds [FS93].

We consider an automaton A′ obtained by “forgetting” the third component of A-transitions, namely for any (q, a, b, p) ∈ E, with a, b ∈ A, the automaton A′ has a transition from q to p on a. If a = b then the weight of this transition is 0, otherwise it is 1. This automaton recognizes Dom(R). Dually, we can define an automaton A′′, which recognizes Ran(R), with a suitable weight function ω′′.

It is not difficult to verify that R is k–reflexive if and only if ω′(A′) ≤ k and ω′′(A′′) ≤ k. ⊓ ⊔

Actually, the problem of deciding whether or not a synchronized rational relation is k–reflexive with respect to the Hamming distance and the problem of computing weights of automata are closely related. Indeed, Theorem 10 shows a reduction in one direction. The converse also holds.

Theorem 11. Given an automaton A = (A, Q, δ, I, F), with a weight function ω, there exists a synchronized rational relation R such that ω(A) is finite if and only if R is almost reflexive.

5 k–reflexivity relative to the edit and to the subword distance

In this section we study the problem of deciding whether or not a relation is k–reflexive with respect to the edit and to the subword distance, respectively. In particular, we show that this problem is solvable for recognizable relations. As in the case of the Hamming distance and of synchronized relations, these results are obtained by means of reductions to the problem of Hashiguchi.

We start by showing the following lemma

Lemma 12. For any recognizable relation R ⊆ A^{∗} × A^{∗} there exists an automaton A with a weight function ω, such that A recognizes Dom(R), and for any x ∈ Dom(R), x ≠ ϵ, ω(x) = min {d_{e}(x, y) | (x, y) ∈ R}.

Proof. (outline) We sketch the proof for R = L′ × L′′ with L′ and L′′ rational languages and L′′ ≠ ∅. The proof can be easily extended to the general case (all recognizable relations are finite unions of relations of this type).

Let A′ = (A, Q′, δ′, q′_{0}, F′) and A′′ = (A, Q′′, δ′′, q′′_{0}, F′′) be two finite deterministic automata accepting the languages L′ and L′′, respectively. We consider the product automaton A = (A, Q, δ, I, F), with Q = Q′ × Q′′, I = {(q′_{0}, q′′_{0})}, F = F′ × F′′, and δ((q′, q′′), a) = {(δ′(q′, a), δ′′(q′′, y)) | y ∈ A^{∗}} for a ∈ A, q′ ∈ Q′, q′′ ∈ Q′′. Intuitively, each A′ transition is “padded” with A′′-paths. The language accepted by A coincides with the language L′ accepted by A′. Moreover, each A-accepting path corresponds to some A′′-accepting path.

We define the weight function ω of A, in such a way that the edit distance between a string x ∈ L′ and the language L′′ can be obtained as the minimum of the weights of accepting paths on x in A. As in the dynamic programming, we obtain the minimum from “local” minima. To this aim, we define ω for q′, p′ ∈ Q′, q′′, p′′ ∈ Q′′, a ∈ A, as follows

ω((q′, q′′), a, (p′, p′′)) = \{ \begin{matrix}∞ & if δ′(q′, a) ≠ p′ or \{y | δ′′(q′′, y) = p′′\} = ∅ \\ 1 & if δ′(q′, a) = p′, q′′ = p′′, and δ′′(q′′, a) ≠ q′′ \\ n & otherwise, \end{matrix}

where n = min({|y| | y ∈ (A − {a})^{∗} and δ′′(q′′, y) = p′′} ∪ {|y| − 1 | y ∈ A^{∗}aA^{∗} and δ′′(q′′, y) = p′′}).

Some comments are now in order. In the first case, the transition from (q′, q′′) to (p′, p′′) on a in A is forbidden either because there is no transition from q′ to p′ on a in A′, or because p′′ is not reachable from q′′ in A′′.

In the second and in the third cases, the symbol a is compared with each string y such that, in the automaton A′′, p′′ is reachable from q′′ on y. Let us denote by L′′_{q′′p′′} the set of such strings. If q′′ and p′′ coincide, then L′′_{q′′p′′} contains the empty string, so the distance between a and L′′_{q′′p′′} is at most 1. More precisely, if a ∉ L′′_{q′′p′′}, i.e., q′′ ≠ δ′′(q′′, a), then this distance is exactly 1 (second case: the symbol a is deleted); otherwise, it is 0 (third case, with y = a).

If states q′′ and p′′ do not coincide, then each string y belonging to L′′_{q′′p′′} contains at least one symbol. If no symbol of y coincides with a, then |y| edit operations are needed to obtain y from a: one operation to replace a by a symbol of y, the other |y| − 1 operations to insert the remaining symbols of y. On the other hand, if a symbol of y coincides with a, then the substitution is not needed; thus, the total number of edit operations is |y| − 1.

It is possible to prove that, for q′, p′ ∈ Q′, q′′, p′′ ∈ Q′′, x ∈ A^{+}, the following equality holds

ω((q′, q′′), x, (p′, p′′)) = \{ \begin{matrix}min & \{d_{e}(x, y) | δ′′(q′′, y) = p′′\} \\ if \{y | δ′′(q′′, y) = p′′\} ≠ ∅ and δ′(q′, x) = p′ \\ ∞ otherwise. \end{matrix}

Thus, for x ∈ L′, x ≠ ϵ, the weight of x in A can be computed as

ω(x)=min {ω((q′_{0}, q′′_{0}), x, (p′, p′′)) | (p′, p′′) ∈ F }=min {d_{e}(x, y) | y ∈ L′′}. ⊓ ⊔

Now, we are able to prove the main result of this section.

Theorem 13. For any recognizable relation R, it is possible to compute the smallest integer k such that R is k–reflexive with respect to the edit distance.

Proof. (outline) Given R ∈ Rec(A^{∗} × A^{∗}), we can define two automata A, A′, with weight functions ω, ω′, respectively, as in Lemma 12. If ϵ ∉ Dom(R) ∪ Ran(R), then we can show that, for k ∈ IN, R is k–reflexive if and only if ω(A) ≤ k and ω′(A′) ≤ k. This allows to compute the smallest k such that R is k–reflexive. The proof can be easily adapted to the case of recognizable relations which contain the empty word in the domain or in the range. ⊓ ⊔

Now, it is natural to investigate whether or not Theorem 13 can be extended to the class of synchronized rational relations. On the one hand, in the case of the Hamming distance we have to compare symbols in corresponding positions, so the fact of having a synchronized transducer is very useful (see the proof of Theorem 10), while in the case of the edit distance we have to compare symbols in different positions: hence, dealing with synchronized relations is of no special help. On the other hand, we are able to prove that given a constant k, the problem of deciding whether or not a synchronized rational relation is k–reflexive relative to the edit distance is solvable. As a consequence, if we know that a synchronized rational relation R is almost reflexive, then we are able to obtain the minimum integer k such that R is k–reflexive (recall that, by Theorem 8, this problem is unsolvable for deteterministic rational relations).

Theorem 14. For any synchronized rational relation R ⊆ A^{∗} × A^{∗} and any integer k ≥ 0, it is possible to decide whether or not R is k–reflexive, with respect to the edit distance.

Proof. For j ≥ 0, let I_{j} = {(u, v) ∈ A^{∗} × A^{∗} | d_{e}(u, v) ≤ j}. Observe that I_{0} = i_{A^{∗}}, I_{1} = i_{A^{∗}} · ((A ∪ {ϵ}) × (A ∪ {ϵ})) · i_{A^{∗}}, and I_{j} = I_{j−1} ∘ I_{1}, where ∘ denotes the composition of relations.

So, the relation I_{1} is rational and has length difference bounded by 1, namely ||u| − |v|| ≤ 1, for (u, v) ∈ I_{1}. By Corollary 4.2 in [FS93], this implies that I_{1} is a synchronized rational relation. Furthermore, the class Syn(A^{∗} × A^{∗}) is closed under composition and intersection. So, R ∩ I_{k} = {(x, y) ∈ R | d_{e}(x, y) ≤ k} ∈ Syn(A^{∗} × A^{∗}), for any k ≥ 0. Hence, R is k–reflexive if and only if the domain and the range of R ∩ I_{k} coincide with the domain and the range of R, respectively. Since domains and ranges of rational relations are rational languages, this property is decidable. ⊓ ⊔

The decidability results relative to the edit distance can be extended even to the subword distance. In particular, by considering a different reduction to the problem of Hashiguchi, it can be shown that the smallest integer k such that a recognizable relation R is k–reflexive, with respect to the subword distance, can be effectively computed. Furthermore, the proof of Theorem 14 can be easily adapted to the subword distance.

Finally, we point out that using the results of [Web94], it is possible to evaluate the complexity of the decision procedures presented in this paper.

References

[Eil74] S. Eilenberg. Automata, languages and machines, volume A. Academic Press, 1974.

[FS93] C. Frougny and J. Sakarovitch. Synchronized rational relations of finite and infinite words. Theoretical Computer Science, 108:45–82, 1993.

[GS66] S. Ginsburg and E. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16:285–296, 1966.

[Has82] K. Hashiguchi. Limitedness theorem on finite automata with distance functions. Journal of Computer and System Sciences, 24:233–244, 1982.

[Has90] K. Hashiguchi. Improved limitedness theorems on finite automata with distance functions. Theoretical Computer Science, 72:27–38, 1990.

[Joh86] J. Johnson. Rational equivalence relations. Theoretical Computer Science, 47:39–60, 1986.

[Kru83] J. Kruskal. An overview of sequence comparison. In D. Sankoff and J. Kruskal, editors, Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, pages 1–44. Addison–Wesley, 1983.

[RS59] M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM J. Res. Develop, 3:125–144, 1959. Also in: E.F. Moore. Sequential machines. Addison–Wesley, 1964.

[Ruo85] K. Ruohonen. Reversible machines and Post’s correspondence problem for biprefix morphisms. J. Inform. Process. Cybernet. EIK, 21:579–595, 1985.

[Web94] A. Weber. Finite–valued distance automata. Theoretical Computer Science, 134:225–251, 1994.