Similarity-based minimization of fuzzy tree automata

摘要

This paper presents a contribution to the problem of similarity-based minimization of deterministic fuzzy finite tree automata (DFFTA). The main question is: how to minimize the number of states of a complete and reduced DFFTA such that the languages of the original automaton and the minimized one be similar but not necessarily equal? Based on extended concepts of fuzzy distance and similarity measures on L-fuzzy sets, we introduce the notion of similarity-based minimal (s-minimal) DFFTA which approximately accepts a fuzzy tree language. Then, a solution for handeling the trade-off between the amount of reduction and the quality of preserving the behavior of system is presented. The paper deals with fuzzy tree automata over complete lattices, but identical results can also be obtained in a more general context for fuzzy tree automata over complete residuated lattices, lattice-ordered monoids, and even for weighted automata over commutative semirings.