Some formal methods for analyzing quantum automata

We survey some formal methods useful in the analysis of (measure-once) 1-way quantum automata (lqfa's). We settle isolated cut point Rabin's theorem in the context of compact monoids; this explains why languages accepted with isolated cut point by several lqfa's models are regular. We recall a nice method in quantum automata theory pointed out by Blondel et al. [9] based on compact groups theory. As an application, we show that it is decidable to test whether two languages accepted by lqfa's are disjoint. Then we discuss some problems on quantum descriptional complexity. In the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages and we present a probabilistic method to construct lqfa's exponentially succinct in the period