We survey some formal methods useful in the analysis of (measure-once) 1-way quantum automata (lqfa's). We settle isolated cut point Rabin's theorem in the context of compact monoids; this explains why languages accepted with isolated cut point by several lqfa's models are regular. We recall a nice method in quantum automata theory pointed out by Blondel et al. [9] based on compact groups theory. As an application, we show that it is decidable to test whether two languages accepted by lqfa's are disjoint. Then we discuss some problems on quantum descriptional complexity. In the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages and we present a probabilistic method to construct lqfa's exponentially succinct in the period.
Some formal methods for analyzing quantum automata / A. Bertoni, C. Mereghetti, B. Palano - In: Descriptional complexity of formal systems / [a cura di] C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke. - Milano : Università degli Studi di Milano, 2005. - pp. 1-14 (( Intervento presentato al 7. convegno International Workshop on Descriptional Complexity of Formal Systems tenutosi a Como nel 2005.
Some formal methods for analyzing quantum automata
A. BertoniPrimo
;C. MereghettiSecondo
;B. PalanoUltimo
2005
Abstract
We survey some formal methods useful in the analysis of (measure-once) 1-way quantum automata (lqfa's). We settle isolated cut point Rabin's theorem in the context of compact monoids; this explains why languages accepted with isolated cut point by several lqfa's models are regular. We recall a nice method in quantum automata theory pointed out by Blondel et al. [9] based on compact groups theory. As an application, we show that it is decidable to test whether two languages accepted by lqfa's are disjoint. Then we discuss some problems on quantum descriptional complexity. In the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages and we present a probabilistic method to construct lqfa's exponentially succinct in the period.File | Dimensione | Formato | |
---|---|---|---|
dcfs05.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
287.64 kB
Formato
Adobe PDF
|
287.64 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.