On the Levenshtein Automaton and the Size of the Neighborhood of a Word

Hélène Touzet (1)

1 BONSAI - Bioinformatics and Sequence Analysis

Given a word P and a maximal number of errors k, we address the problem of counting the number of strings whose Levenshtein distance to P does not exceed k. We give an algorithm that scales linearly with the size of P and that is based on a variant of the classical Levenshtein automaton.

Domaines: Algorithme et structure de données [cs.DS]

Hélène Touzet. On the Levenshtein Automaton and the Size of the Neighborhood of a Word. LATA 2016 - 10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. pp.207-218, ⟨10.1007/978-3-319-30000-9_16⟩. ⟨hal-01360482⟩