Quantum automata for some multiperiodic languages |
| |
Authors: | Carlo Mereghetti Beatrice Palano |
| |
Affiliation: | Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano, via Comelico 39/41, 20135 Milano, Italy |
| |
Abstract: | 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. |
| |
Keywords: | Quantum automata Periodic languages |
本文献已被 ScienceDirect 等数据库收录! |