# Efficient Algorithms for Computing the Inner Edit Distance of a Regular Language via Transducers
## 1 Introduction  
The concept of edit distance and its variants has applications in many areas such as computational linguistics [1], bioinformatics [2], and synchronization error detection in data communications [3]. The edit distance of a language \(L\) with at least two words--also referred to as _inner edit distance_ of \(L\)--is the minimum edit distance between any two different words in \(L\). In [4], the author considers the problem of computing the edit distance of a regular language, which is given via a Nondeterministic Finite Automaton (NFA), or a Deterministic Finite Automaton (DFA). For a given automaton \(\mathbf{a}\) with \(n\) transitions and an alphabet of \(r\) symbols, the algorithm proposed in [4] has worst-case time complexity  
\[O(r^{2}n^{2}q^{2}(q+r)), \tag{1}\]  
where \(q\) is either the number of states in \(\mathbf{a}\) (if \(\mathbf{a}\) is a DFA), or the square of the number of states in \(\mathbf{a}\) (if \(\mathbf{a}\) is an NFA). If the size of the alphabet is ignored and the automaton in question has only states that can be reached from the start state, then the number of states is \(O(n)\) and the worst-case time complexity shown in Label (1) can be written as  
\[O(n^{5})\text{ for DFAs, and }O(n^{8})\text{ for NFAs.} \tag{2}\]In this paper, we present two efficient algorithms to compute the inner edit distance of a regular language given via an NFA with \(n\) transitions--see Theorems 1 and 3. Both algorithms, which are called DistErrDetect and DistInpAlter, have the same worst-case time complexity  
\[O(n^{2}dr^{2}), \tag{3}\]  
where \(d\) is the computed distance, which is a significant improvement over the original algorithm in [4]. Our first algorithm, DistErrDetect, is based on the general method of [5] for computing distances via the error-detection property. Now, however, we have an efficient way of realizing algorithmically that general method using an incremental construction of a (nondeterministic) transducer and the test of [6] for partial identity for transducers. In our second algorithm, DistInpAlter, the idea is to model the edit operations of the desired distance using an efficient, in terms of size, input-altering transducer (a transducer whose output is always different from the input used). Please see subsequent sections for definitions of terms. For clarity of presentation, we give in detail not only the new algorithms, but also their preliminary versions PrelimDistErrDetect and PrelimDistInpAlter that could possibly be applied to other types of distances. We have implemented the preliminary and final versions of the second algorithm (PrelimDistInpAlter and DistInpAlter) in Python using the well maintained, open source package FAdo for automata [7]. We have also tested our implementation experimentally, and we present in this paper the outcomes of the tests. We note that some related problems involving distances between words and languages can be found in [8; 9] (edit distance between a word and a language), and in [10; 11; 12; 13; 14] (various distances between two languages). Also in [15], the newer concept of edit distance with moves is investigated. The problem considered here is technically different, however, as the desired distance involves _different words_ within the _same_ language. More specifically, if we used directly the tools of [10; 11], for instance, to compute an edit string with minimal number of errors between the given language and itself, then that string would simply be an edit string of zero errors, as the edit distance between any word and itself is zero. We also note that the inner prefix distance of a regular language, which is quite different from the inner edit distance, is considered in [16] and computed in time \(O(n^{2}\log n)\). The paper is organized as follows. The next section contains basic notions on languages, word relations, finite-state machines and edit-strings.