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.
Quantum automata for some multiperiodic languages / C. Mereghetti, B.S. Palano. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 387:2(2007 Nov), pp. 177-186. ((Intervento presentato al 8. convegno International Workshop on Descriptional Complexity of Formal Systems tenutosi a Las Cruces nel 2006.
Quantum automata for some multiperiodic languages
C. Mereghetti
;B.S. PalanoUltimo
2007
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.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
298.9 kB
Formato
Adobe PDF
|
298.9 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.