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. Mereghetti
Primo
;
B. Palano
Ultimo
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.
Periodic languages; Quantum automata
Settore INF/01 - Informatica
2006
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/26979
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact