Automata theory based on quantum logic: Reversibilities and pushdown automata

AbstractAutomata theory based on quantum logic, called l-valued finite automata (l-VFAs), may be viewed as a logical approach to quantum computing. This work is mainly divided into two parts: one part deals with reversibility of l-VFAs, and the other establishes a basic framework of l-valued pushdown automata (l-VPDAs). First we provide some preliminaries concerning quantum logic and l-VFAs, and we prove a useful property of l-valued successor and source operators. Then we clarify the relationships between various reversibilities closely related to quantum finite automata in the literature. In particular, we define a reversibility of l-VFAs which is termed as retrievability, and we clarify the relationships between a number of different fashions regarding retrievability of l-VFAs. We prove that some of them are equivalent, but for the others to be equivalent the truth-value set is required to satisfy a certain condition. This is an essential difference from the classical situation. Afterwards, we introduce l-VPDAs and show that the class of the languages accepted by l-VPDAs by empty stack coincides with that accepted by l-VPDAs by final state. Finally, we provide some examples of l-VFAs and conclude with some remarks