Quantum Automata for some Multiperiodic Languages.
Carlo Mereghetti, Beatrice Palano · DCFS · 2006
We exhibit small size measure-once one-way quantum finite automata (mo-1qfa's) inducing multiperiodic stochastic events. Moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point mo-1qfa's whose size logarithmically depends on the periods; (ii) Monte Carlo mo-1qfa's whose size logarithmically depends on the periods and polynomially on the inverse of the error probability.