Quantum logic and automata theory
- Publication Type:
- Handbook of Quantum Logic and Quantum Structures, 2007, pp. 619 - 754
- Issue Date:
It is noted that a theory of computation based on quantum logic is to be established as a logical foundation of quantum computation. Finite automata and pushdown automata are considered the simplest abstract mathematical models of computing machines. Automata theory is an essential part of computation theory. This chapter describes a systematic exposition of automata theory. In context to this theory, quantum logic is treated as an orthomodular lattice-valued logic. The approach employed in developing this theory is essentially the semantical analysis. This chapter introduces notions of orthomodular lattice-valued finite automata and pushdown automata and their various variants. It defines the classes of languages accepted-namely, orthomodular lattice-valued regular languages and context-free languages. This chapter also re-examines various properties of automata in the framework of quantum logic, including the Kleene theorem concerning equivalence between finite automata and regular expressions, equivalence between pushdown automata and context-free grammars, and the pumping lemma both for regular languages and for context-free languages. © 2007 Copyright © 2007 Elsevier B.V. All rights reserved.
Please use this identifier to cite or link to this item: