### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 3471-3480 |

Number of pages | 10 |

Journal | Theoretical Computer Science |

Volume | 410 |

Publication status | Published - 2009 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'From Nerode’s congruence to suffix automata with mismatches'. Together they form a unique fingerprint.

## Cite this

Epifanio, C., Crochemore, M., Mignosi, F., & Gabriele, A. (2009). From Nerode’s congruence to suffix automata with mismatches.

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