Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton

Simple item page
dc.creatorAllauzen, Cyril
dc.creatorMohri, Mehryar
dc.date2009-04-29
dc.date.accessioned2026-07-07T13:10:00Z
dc.date.available2026-07-07T13:10:00Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/0904.4686
dc.identifierhttp://arxiv.org/abs/0904.4686
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228925
dc.subjectFormal Languages and Automata Theory
dc.titleLinear-Space Computation of the Edit-Distance between a String and a Finite Automaton
dc.typetext

Files

Collections

arXiv