### Abstract

Lingua originale | English |
---|---|

pagine (da-a) | 3471-3480 |

Numero di pagine | 10 |

Rivista | Theoretical Computer Science |

Volume | 410 |

Stato di pubblicazione | Published - 2009 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cita questo

*Theoretical Computer Science*,

*410*, 3471-3480.

**From Nerode’s congruence to suffix automata with mismatches.** / Epifanio, Chiara; Crochemore, Maxime; Mignosi, Filippo; Gabriele, Alessandra.

Risultato della ricerca: Article

*Theoretical Computer Science*, vol. 410, pagg. 3471-3480.

}

TY - JOUR

T1 - From Nerode’s congruence to suffix automata with mismatches

AU - Epifanio, Chiara

AU - Crochemore, Maxime

AU - Mignosi, Filippo

AU - Gabriele, Alessandra

PY - 2009

Y1 - 2009

N2 - In this paper we focus on the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. As first results we give acharacterization of the Nerode''s right-invariant congruence that is associated withS_k. This result generalizes the classical characterization described in [5]. As secondresult we present an algorithm that makes use of S_k to accept in an efficient waythe language of all suffixes of w up to k errors in every window of size r of a text,where r is the repetition index of w. Moreover, we give some experimental results onsome well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally,we state a conjecture and an open problem on the size and the construction of thesuffix automaton with mismatches.

AB - In this paper we focus on the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. As first results we give acharacterization of the Nerode''s right-invariant congruence that is associated withS_k. This result generalizes the classical characterization described in [5]. As secondresult we present an algorithm that makes use of S_k to accept in an efficient waythe language of all suffixes of w up to k errors in every window of size r of a text,where r is the repetition index of w. Moreover, we give some experimental results onsome well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally,we state a conjecture and an open problem on the size and the construction of thesuffix automaton with mismatches.

KW - Approximate string matching

KW - Combinatorics on words

KW - Indexing

KW - Languages with mismatches

KW - Suffix Automata

UR - http://hdl.handle.net/10447/40047

M3 - Article

VL - 410

SP - 3471

EP - 3480

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -