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.
Events and Languages on Unary Quantum Automata / M.P. Bianchi, B. Palano - In: Non-Classical Models of Automata and Applications (NCMA)Vienna : Austrian Computer Society, 2009. - ISBN 9783854032564. - pp. 61-75 (( Intervento presentato al 1. convegno Non-Classical Models of Automata and Applications tenutosi a Wroclaw nel 2009.
Events and Languages on Unary Quantum Automata
B. PalanoUltimo
2009
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
ncma09.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
199.52 kB
Formato
Adobe PDF
|
199.52 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.