On the Levenshtein Automaton and the Size ...

Document type :
Communication dans un congrès avec actes
DOI :
10.1007/978-3-319-30000-9_16
Title :
On the Levenshtein Automaton and the Size of the Neighborhood of a Word
Author(s) :
Touzet, Helene [Auteur] refId
Bioinformatics and Sequence Analysis [BONSAI]
Scientific editor(s) :
Adrian-Horia Dediu
Jan Janoušek
Carlos Martín-Vide
Bianca Truthe
Conference title :
LATA 2016 - 10th International Conference on Language and Automata Theory and Applications
City :
Prague
Country :
République tchèque
Start date of the conference :
2016-03-14
Journal title :
Lecture Notes in Computer Sciences
Publisher :
Springer
Publication date :
2016
HAL domain(s) :
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
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 ...
Show more >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Harvested from HAL
Files
Thumbnail
Thumbnail
Thumbnail
Thumbnail
Thumbnail