On Relation Between Linear Temporal Logic and Quantum Finite Automata

摘要

Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. The relationship between theory of automata and logic had a great influence in the computer science. Investigation of the relationship between quantum finite automata and linear temporal logic is a natural goal. In this paper, we present a construction of quantum finite automata on finite words from linear-time temporal logic formulas. Further, the relation between quantum finite automata and linear temporal logic is explored in terms of language recognition and acceptance probability. We have shown that the class of languages accepted by quantum finite automata are definable in linear temporal logic, except for measure-once one-way quantum finite automata.