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. Palano
Ultimo
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.
Quantum automata ; Periodic languages
Settore INF/01 - Informatica
nov-2007
Article (author)
File in questo prodotto:
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.

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