Behaviours of Unary Quantum Automata

Issue title: Non-Classical Models of Automata and Applications

Article type: Research Article

Authors: Bianchi, Maria Paola | Palano, Beatrice

Affiliations: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39 – 20135 Milano – Italy. maria.bianchi@unimi.it | Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39 – 20135 Milano – Italy. palano@dsi.unimi.it

Note: [] Address for correspondence: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy.

Abstract: We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased.

Keywords: Quantum automata, periodic events, unary languages

DOI: 10.3233/FI-2010-333

Journal: Fundamenta Informaticae, vol. 104, no. 1-2, pp. 1-15, 2010