We construct small size measure-once 1qfa's inducing multiperiodic stochastic events. Moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point 1qfa's whose size logarithmically depends on the periods; (ii) Monte Carlo 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. Palano - In: Descriptional Complexity of Formal Systems / [a cura di] H. Leung, G. Pighizzini. - Las Crucias : NM State University - Las Cruces, 2006. - pp. 199-210 (( Intervento presentato al 8. convegno Descriptional Complexity of Formal Systems tenutosi a Las Cruces nel 2006.
Quantum automata for some multiperiodic languages
C. MereghettiPrimo
;B. PalanoUltimo
2006
Abstract
We construct small size measure-once 1qfa's inducing multiperiodic stochastic events. Moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point 1qfa's whose size logarithmically depends on the periods; (ii) Monte Carlo 1qfa's whose size logarithmically depends on the periods and polynomially on the inverse of the error probability.
| File | Dimensione | Formato | |
|---|---|---|---|
|
dcfs06.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
256.74 kB
Formato
Adobe PDF
|
256.74 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.
