Fuzzy automata with epsilon-moves compute fuzzy measures between strings
This paper introduces fuzzy automata with transitions by empty string (epsilon-moves), and shows their relationship with other classes of classical fuzzy automata. The c-move represents a state change of the automaton without consuming any symbol of the input string. In approximate string matching, epsilon-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 epsilon-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 epsilon-moves that computes it, is also proposed. (C) 2006 Elsevier B.V. All rights reserved.
fuzzy automata fuzzy measures approximate string matching fuzzy system models pattern recognition