Fuzzy automata with ε-moves compute fuzzy measures between strings

摘要

This paper introduces fuzzy automata with transitions by empty string (ε-moves), and shows their relationship with other classes of classical fuzzy automata. The ε-move represents a state change of the automaton without consuming any symbol of the input string. In approximate string matching, ε-moves allow to model the effect of the insertion of a symbol (one of the possible edit operations). We provide a fuzzy measure between strings based on the concepts of string alignments and fuzzy edit operations. The main contribution of this paper is to prove that a particular class of fuzzy automata with ε-moves computes those fuzzy measures without restricting the number of errors between the strings. Given a fuzzy measure, a building method for constructing the fuzzy automaton with ε-moves that computes it, is also proposed.