Quantum Automata for some Multiperiodic Languages.
Carlo Mereghetti, Beatrice Palano
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.
DCFS•Jan 1, 2006•0 citations