From Nerode’s congruence to suffix automata with mismatches

In this paper we focus on the minimal deterministic finite automaton _Sk$S_k$ that recognizes the set of suffixes of a word w$w$ up to k$k$ errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with _Sk$S_k$. This result generalizes the classical characterization described in A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of _Sk$S_k$ to accept in an efficient way the language of all suffixes of w$w$ up to k$k$ errors in every window of size r$r$ of a text, where r$r$ is the repetition index of w$w$. Moreover, we give some experimental results on some 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 the suffix automaton with mismatches.