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. Bertoni
Primo
;
C. Mereghetti
Secondo
;
B. Palano
Ultimo
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.
Settore INF/01 - Informatica
2005
International Federation for Information Processing
Book Part (author)
File in questo prodotto:
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.

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