Grid Value Minimize Tree Automata

The minimization of finite automata is of importance in reserching program test, fuzzy system, probabilistic automata and so on. If finite automata have less states, more hardware resource and soft resource can be saved on the premise of equivalence of finite automata. Tree automata is a extended form of finite automata and weighted tree automata is a generalization of tree automata, they have many applications, such as model checking and natural language processing. The scale and minimization of finite automata are very important to the above applications. Hence, so many researchers are interested in the minimization problem of finite automata.In 1954 Huffman presented a minimization algorithm of classical deterministic finite automata, afterwards, Moore and Hopcroft gave more effective algorithms. Hogberg and Maletti discussed the minimization of tree automata and weighted tree automata and provided related algorithms. Recently, Y.M.Li and H.X.Lei study the minimization of deterministic lattice-valued automata and complete lattice-valued finite automata respectively; in the meantime, the related minimization algorithms are given.Inspired by some existing ideas and methods, we are concerned with tree au-tomata based on lattice-ordered monoids, which is a generalization of tree automata and fuzzy finite automata and considered as a special weighted tree automata. There are so abundant theoretical achievements about tree automata, fuzzy finite automata and weighted tree automata. The minimization is a very active subject in the au-tomata theory. We study the minimization of tree automata based on lattice-ordered monoids from congruence relations and bisimulation relations. The main contents follow as:1 First, we present congruence relations of deterministic recognizable tree se-ries. Secondly, we give a theory of minimization of deterministic all-accepting L-fta and prove a Myhill-Nerode theory of deterministic all-accepting L-fta. Finally, a characteristic of deterministic recognizable tree series is obtained.2 Concepts of forward and backward bisimulations for a L-fta are defined and the quotient L-fta by them are obtained. Moreover, the equivalence of a L-fta and its quotient L-fta and the existence of minimal forward L-fta and minimal backward L-fta are proved. An algorithm for computing the greatest forward bisimulation is presented in finite steps.