Similarity Approximation of Nondeterministic Fuzzy Tree Automata

Nondeterministic fuzzy tree automata (NFTA) are a generalization of finite word automata and tree automata that process tree structures with a fuzzy behavior. This paper presents a novel method for approximating the fuzzy similarity of two systems presented by NFTA. The main idea is intruducing a hybrid similarity approximation scheme by realizing the relations between the structural similarity of systems and the similarity of internal states of them. In this regard, firstly, we generalize the concepts of distance and similarity measures between fuzzy sets to the states of NFTA. Then, the consistency between the concepts of similarity and approximate similarity of two NFTA are characterized with a behavioral approach. Finally, we develope an efficient algorithm for the similarity approximation.