Abstract. The problem of computing the edit-distance between a string and a finite automaton arises in a variety of applications in computational biology, text processing, and speech recognition. This paper presents linear-space algorithms for computing the edit-distance between a string and an arbitrary weighted automaton over the tropical semiring, or an unambiguous weighted automaton over an arbitrary semiring. It also gives an efficient linear-space algorithm for finding an optimal alignment of a string and such a weighted automaton.
A space efficient algorithm for computing the edit distance between a string and a weighted automaton over a tropical semiring was developed in REF .
Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton
ArXiv
ArXiv
Mathematics Computer Science