Geodesic
Dynamic programming for reduced NFAs for approximate string and sequence matching
Kybernetika, Tome 38 (2002) no. 1, p. [81]

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

searching for all occurrences of a pattern (string or sequence) in some text, where the pattern can occur with some limited number of errors given by edit distance. Several methods were designed for the approximate string matching that simulate nondeterministic finite automata (NFA) constructed for this problem. This paper presents reduced NFAs for the approximate string matching usable in case, when we are interested only in occurrences having edit distance less than or equal to a given integer, but we are not interested in exact edit distance of each found occurrence. Then an algorithm based on the dynamic programming that simulates these reduced NFAs is presented. It is also presented how to use this algorithm for the approximate sequence matching.
Classification : 68P10, 68Q45, 68T10, 68W05, 68W32, 90C39
Keywords: string and sequence matching; nondeterministic finite automata 
@article{KYB_2002__38_1_a4,
     author = {Holub, Jan},
     title = {Dynamic programming for reduced {NFAs} for approximate string and sequence matching},
     journal = {Kybernetika},
     pages = {[81]},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2002},
     mrnumber = {1899848},
     zbl = {1265.68042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a4/}
}
TY  - JOUR
AU  - Holub, Jan
TI  - Dynamic programming for reduced NFAs for approximate string and sequence matching
JO  - Kybernetika
PY  - 2002
SP  - [81]
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a4/
LA  - en
ID  - KYB_2002__38_1_a4
ER  - 
%0 Journal Article
%A Holub, Jan
%T Dynamic programming for reduced NFAs for approximate string and sequence matching
%J Kybernetika
%D 2002
%P [81]
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a4/
%G en
%F KYB_2002__38_1_a4
Holub, Jan. Dynamic programming for reduced NFAs for approximate string and sequence matching. Kybernetika, Tome 38 (2002) no. 1, p. [81]. http://geodesic.mathdoc.fr/item/KYB_2002__38_1_a4/