Depicts Several Types Of Automata Based On Quantum Logic Algebra And Logic

The ideas of quantum computing came from the connections between physics and computation. Due to reversibility, an important characteristic of quantum physics, as it relates to quantum computing, in 1973, Bennett proved that any given Turing machine can be efficiently simulated by a reversible one. In 1980, Benioff en-visaged a sort of Turing computing model based on quantum mechanics principles, and verified they could simulate classical reversible Turing machines. Before long, Feynman then proposed an essential guess that the computing speed of classical Turing machines simulating some quantum phenomena was likely decreasing expo-nentially. After that, by formalizing Benioff and Feynman's ideas, Deutsch in 1985 re-examined the Church-Turing principle, and defined quantum Turing machines. In particular, in 1994 Shor discovered a polynomial-time algorithm for factoring prime on quantum computers, and Grover then found an algorithm for searching through a database in square root time. Since then, quantum computing has attracted more and more attention in the research community.In this field, the computing model of quantum computation is still one of the most important topic to study. Quantum finite automata can be viewed as a kind of quantum computer model with finite memory. A more fundamental issue regarding quantum computing models may be automata theory based on quantum logic(also called orthomodular lattice-valued automata),in which quantum logic is understood as a logic whose truth-value set is an orthomodular lattice, and an element of an or-thomodular lattice is assigned to each transition of an automaton and it is considered to be the truth value of the proposition describing the transition. Thus, investigat-ing orthomodular lattice-valued automata may be considered to be an important aspect of the logical basic of quantum computing. This also is a logical approach to quantum computation in which the ultimate objective is to set up the logic platform for the quantum computation, and it should be treated as a further abstraction of mathematical models of quantum computation. With this approach, the author dealt with some operations on L-valued automata, and interestingly established lots of corresponding important theorem. As shown by Ying, the validity of some important theorem is strongly dependent on the commutators of the corresponding orthomodular lattice, and the complete validity of these theorem is equivalent to the distribution of the used orthomodular lattice, and the underlying logic is de-generated to classical two-valued Boolean logic. Soon after that, by deep analysis of orthomodular lattice-valued automata which are proposed by Ying and algebraic properties of orthomodular lattice, Li introduce the extended subset constructions, by using this, the authors have shown the fact that a lot of important theorems and the corresponding conclusions such as Kleene theorem in automata theory based on quantum logic are indeed hold no matter whether the distributive law(commutator) truly hold or not, which in turns deepen and advance the automata theory based on quantum logic.In this thesis, by using semantic analysis and also the means of quantum state construction which proposed by the author also revised from the extended subset constructions introduced by Li, we mainly further continue this study in these area such as Pushdown automata, Biichi automata, Muller automata explicitly in the underlying quantum logic in details in which distributivity laws fail, we also take into account some corresponding algebraic and logical characterizations of them in the mean time, which aims to obtain comparatively more integrated and essential also even profound enough results.The specific structure and the main results of this thesis are enumerated as follows:(1) Algebraic characterizations of pushdown automata based on quantum logic.Firstly, the notion of orthomodular lattice-valued pushdown automaton quantum pushdown automata(abbr. LVPDA) is introduced, we also provide the means of general quantum state construction, and we further prove the fact that an LVPDA can accept the same valued language by final states and by another LVSPDA with the crisp transition relation and fuzzy final states in the mean time, and also show that LVPDA can accept the same L—valued languages by final states and by empty stack. By using this equivalent relations, we establish some algebraic and level characterizations of orthomodular lattice-valued context-free languages, and also deal with the closed properties of these L-valued languages in details under some regular operations in particular at the same time. Secondly, we provide the concept of orthomodular lattice-valued Context-free grammar(abbr. LVCFG), and traverse some algebraic characterizations of this grammar in details, we also show that orthomodular lattice-valued Chomsky Normal Forms(abbr. LVCVF) and orthomodular lattice-valued Greibach Normal Forms(abbr. LVGNF) of LVCFG are mutually equivalently constructed in the mean time. Thirdly, we present an arbitrary orthomodular lattice-valued context-free grammar(abbr. LVCFG) and an LVPDA are mutually equivalently constructed as well. Finally, based on these algebraic characterizations of LVCFG, the pumping lemma of orthomodular lattice-valued context-free language, which decide whether an orthomodular lattice-valued language is an orthomodular lattice-valued context-free language or not.(2) Algebraic characterizations of Buchi automata based on quantum logic.The concept of orthomodular lattice-valued Buchi automata (abbr. LVBA) is introduced, we traverse some algebraic properties of this automata in details. By noticing that the finiteness of the image set of the languages which a given LVBA is accepted, we provide the notion of L—valued recognizable finite step language, also by combine the means of quantum state construction which we provided, we obtain the algebraic,level and Biichi characterizations of orthomodular lattice-valued regu-larω—languages. Also by introducing the L-valuedω-regular expression, thereby this in turn can denote the quantumω-languages (quantum infinite languages), we further establish L-valuedω-Kleene theorem, however which give the equivalent algebraic characterizations of L-valuedω-languages recognized by LVMA.(3) Algebraic characterizations of Muller automata based on quantum logic.Firstly, the definition of orthomodular lattice-valued Miiller automata(LVMA in short) is introduced, we traverse some algebraic properties of this automata in details. By noticing that the finiteness of the image set of the languages which a given LVMA is recognized, we provide the concept of L-valued recognizable fi-nite step language, also by combine the means of quantum state construction which we provied, we prove the fact that LVMA and orthomodular lattice-valued deter-ministic Muller automata(abbr. CVDMA) can equivalently constructed from each other, Simultaneously, we investigate the algebraic and level characterizations of or-thomodular lattice-valued regularω-languages particularly; Secondly, we deal with the closed properties of these L-valued languages in details under someω-regular operations in particular at the same time. Finally, we present the equivalent rela-tions between LVBA and LVBA, and also establish the generalized McNaughton theorem based on quantum logic.(4) Logical characterizations of Muller automata based on quantum logic.Firstly, by introducing the concept of monadic second-order quantum logic(abbr. LVMSO), we obtained the monadic second-order logic description of orthomodu-lar lattice-valued regularω-languages which a given LVMA is recognized,i.e. we prove the fact that the behaviours of orthomodular lattice-valued Muller automata are precisely the quantum languages definable with sentences of the LVMSO, which deepen and generalize the fundamentalω-Buchi theorem;Secondly, by introduc-ing the notions of L-valued star-freeω-regular language and L-valued aperiodicω-regular language, respectively, and also traverse some algebraic feature of these languages in details, we successfully show that L-valued star-freeω-regular lan-guage and L-valued aperiodicω-regular language introduced here coincide with the first-order definable ones, which generalizes the classical classification theorem to quantum logic setting.