College of Computer Science, Shaanxi Normal University, Xi’an 710062, China

We introduce monadic second-order quantum logic and prove that the behaviors of finite automata based on quantum logic are precisely the quantum languages definable with sentences of our monadic secondorder quantum logic. This generalizes B¨uchi’s and Elgot’s fundamental theorems to quantum logic setting. We also consider first-order quantum logic and show that star-free quantum languages and aperiodic quantum languages introduced here coincide with the first-order quantum definable ones. This generalizes Sch¨utzenberger’s fundamental theorems to quantum logic setting. The determinazation of finite automata based on quantum logic is studied by introducing the generalized subset construction method. Then the Kleene theorem in the frame of quantum logic is presented here.

This work was supported by the National Natural Science Foundation of China (Grant Nos. 10573112, 60873119), and the Research Foundation for the Doctorial Program of Higher School of Ministry of Education of China (Grant No. 200807180005).