The Algebraic Properties Of Quantum Finite Tree Automata

The tree automata play a key role in the theory of computation.On the one hand,it is the important basis of modern computer science,on the other hand,it is also one of the most important mathematical models of computation theory.The weighted tree automata is the generalization of classical finite tree automata,which is formed by adding weights on the transition of the finite tree automata,and these weights are usually valued in the algebraic structures such as semirings and so on.In 1936,Birkhoff and Neumann put forward the concept of quantum logic for the first time.Furthermore,Ying M.S defined quantum logic as complete orthomodular lattice-valued logic,then the theory of automata based on quantum logic is proposed,which is called quantum automata,and some operational properties problems of quantum automata are discussed.Finite tree automata and tree language are important research directions of tree automata theory.In the classical tree automata theory,the nondeterministic finite tree automata are equivalent to the deterministic finite tree automata.We known,the Pumping Lemma and Kleene Theorem of regular tree language,which are valued in various algebraic structures,are also one of the research areas of in-terest.Thus this paper investigates the Pumping Lemma and Kleene Theorem of quantum regular tree language,we introduce the definitions and explore the relation-ships of nondeterministic quantum finite tree automata,simplified nondeterministic quantum finite tree automata,nondeterministic quantum finite tree automata with?-rules,top down nondeterministic quantum finite tree automata and top down de-terministic quantum finite tree automata.the main results of this thesis are arranged as follows:1.We introduce the algebraic properties of quantum finite tree automata.Firstly,the notions of nondeterministic quantum finite tree automata,simplified nondeterministic quantum finite tree automata,nondeterministic quantum finite tree automata with ?-rules and deterministic quantum finite tree automata,top down nondeterministic quantum finite tree automata and top down deterministic quantum finite tree automata are given,in the meanwhile two quantum regular tree languages are defined in breadth-first and depth-first manners respectively,and the sufficient and necessary condition when they are equivalent is given.Second-ly,the equivalence of nondeterministic finite tree automata and deterministic finite tree automata is proved under the framework of quantum logic.Finally,it turns out that nondeterministic quantum finite tree automata,simplified nondeterminis-tic quantum finite tree automata,nondeterministic quantum finite tree automata with(?)-rules,deterministic quantum finite tree automata top down nondeterministic quantum finite tree automata are equivalent to each other.2.The algebraic properties of quantum regular tree language are studied.In the first part,algebraic characterization and level characterization of the quantum regular tree language are investigated.In the second part,the Pumping Lemma of the quantum regular tree language is demonstrated,and an example is given to illustrate it.In the third part,the regular operation of quantum regular tree language is defined,and it is closed under the operation is proved.Then,the tree language is equivalent to the regular tree expression under the framework of quantum logic is proved by introducing quantum regular tree expression,that is,the Kleene Theorem of quantum regular tree language holds.