MERGING STATES IN DETERMINISTIC FUZZY FINITE TREE AUTOMATA BASED ON FUZZY SIMILARITY MEASURES

Abstract

This paper presents a contribution to the problem of measuring fuzzy similarity of states and merging them in a Deterministic Fuzzy Finite Tree Automaton (DFFTA).  The main question is: how to merge some states of a complete and reduced DFFTA such that the languages of original automaton and minimized one be similar but not necessarily equal? In order to solving this problem, we generalize the concepts of distance and similarity measures between fuzzy sets to distance and similarity measures between states of DFFTA.  Then, we define the notions of normal DFFTA and introduce an efficient algorithm (polynomial order of time complexity) for discovering similar state sets of a DFFTA.