We study the phenomenon of periodicity on quantum automata from three points of view. First, we provide an efficient algorithm for testing the periodicity of stochastic events induced by measure-once one-way unary quantum automata (1qfa’s). Second, we design an algorithm for the synthesis of succinct unary 1qfa’s inducing periodic events. To evaluate the size of the resulting 1qfa’s, we relate the number of states of a minimal 1qfa inducing a linear approximation of a periodic event p to the harmonic structure of p. Next, we study the complexity of our synthesis algorithm. Third, we apply our synthesis algorithm for building succinct 1qfa’s that accept unary periodic languages. We also prove a lower bound on the size of 1qfa’s accepting unary periodic languages.
Quantum automata and periodic events / C. Mereghetti, B. Palano (MATHEMATICS, COMPUTING, LANGUAGE, AND LIFE: FRONTIERS IN MATHEMATICAL LINGUISTICS AND LANGUAGE THEORY). - In: Scientific Applications of Language Methods / [a cura di] C. Martin-Vide. - London : Imperial College press, 2010. - ISBN 9781848165441. - pp. 563-584 [10.1142/9781848165458_0011]
Quantum automata and periodic events
C. MereghettiPrimo
;B. PalanoUltimo
2010
Abstract
We study the phenomenon of periodicity on quantum automata from three points of view. First, we provide an efficient algorithm for testing the periodicity of stochastic events induced by measure-once one-way unary quantum automata (1qfa’s). Second, we design an algorithm for the synthesis of succinct unary 1qfa’s inducing periodic events. To evaluate the size of the resulting 1qfa’s, we relate the number of states of a minimal 1qfa inducing a linear approximation of a periodic event p to the harmonic structure of p. Next, we study the complexity of our synthesis algorithm. Third, we apply our synthesis algorithm for building succinct 1qfa’s that accept unary periodic languages. We also prove a lower bound on the size of 1qfa’s accepting unary periodic languages.File | Dimensione | Formato | |
---|---|---|---|
coll11.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
402.72 kB
Formato
Adobe PDF
|
402.72 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.