We prove that any unary regular language can be accepted with constant cut point and isolation by a MM-qfa with an amount of states which is linear in the size of the corresponding dfa. This gives a characterization of the recognition power of unary MM-qfa’s. We also single out families of unary languages for which the size of the accepting MM-qfa’s can be exponentially decreased. Then, we give an algorithm for testing the d-periodicity of the events induced by unary MM-qfa’s. Finally, we show how to compute the dimension of the “ergodic” and “transient” subspaces of unary MM-qfa’s. These algorithms run in polynomial time on unary MM-qfa’s having complex amplitudes with rational components.
|Titolo:||Events and Languages on Unary Quantum Automata|
PALANO, BEATRICE SANTA (Ultimo)
|Parole Chiave:||Quantum automata; unary languages; periodic events|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2009|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|