The Equivalence And Approximation Of Fuzzy Tree Automata Based On T-module

The tree automata is an important mathematical model in computing theory.It is not only indispensable to the research of computer science,but also be widely used in other fields.But the tree language recognized by classical tree automata has some shortcomings in describing fuzzy uncertainty.As a formal model of a kind of fuzzy algorithm or fuzzy computation,the fuzzy tree automata has important applications in the determinability of fuzzy logic and the detection of multivalued models.The max-*compound algorithm proposed by Zadeh in 1965 is the most common inference method in fuzzy system,in which*is the t-norm.To further enrich and promote computing theory under the fuzzy logic framework,this thesis mainly establishes a kind of computing models based on t-norm.We discuss the relations among the several kinds of fuzzy tree automata and the closure of fuzzy tree language to regular operations.Meanwhile,the approximation and the robustness of fuzzy tree automata are obtained.The main content of this thesis is as follows:1.The first,several concepts of fuzzy tree automata based on t-norm are pro-posed.Using semantic analysis method and generalized subset construction tech-nique,the equivalence relations among the nondeterministic fuzzy tree automata(abbr.NFTA*),deterministic fuzzy tree automata(abbr.DFTA*),nondeterministic fuzzy tree automata with empty transfer(abbr.NFTA*?),simplified nondetermin-istic fuzzy tree automata(abbr.SNFTA*),nondeterministic top-down fuzzy tree automata(abbr.NFTA*?)and deterministic top-down fuzzy tree automata(abbr.DFTA*?)are proved when t-norm meets the finite generated condition(abbr.FGC).The second,the closure of fuzzy tree language for regular operations is studied,ob-tained that fuzzy tree language under any t-norm is not closed for"complement".2.It is discussed that if t-norm meets the weakly finite generated condition(abbr.WFGC),the nondeterministic fuzzy tree automata and deterministic fuzzy tree automata are equivalent in the sense of approximation.That is to say,the nondeterministic fuzzy tree automata can be approximated by deterministic fuzzy tree automata with arbitrary precision,and the corresponding structure is given.Also,we define the approachable relation between two nondeterministic fuzzy tree automata and deterministic fuzzy tree automata based on t-norm,and then,the robustness of fuzzy tree automata based on t-norm is studied.