In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed ($\MON$-1qfa). The automaton works on a compatibility alphabet $(\Sigma, E)$ of observables and its probabilistic behavior is a formal series on the free partially commutative monoid $\FI(\Sigma, E)$ with idempotent generators. We prove some properties of this class of formal series and we apply the results to analyze the class $\LMO(\Sigma, E)$ of languages recognized by $\MON$-1qfa's with isolated cut point. In particular, we prove that $\LMO(\Sigma, E)$ is a boolean algebra of recognizable languages with finite variation, and that $\LMO(\Sigma, E)$ is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.
Trace monoids with idempotent generators and measure-only quantum automata / A. Bertoni, C. Mereghetti, B. Palano. - In: NATURAL COMPUTING. - ISSN 1567-7818. - 9:2(2010), pp. 383-395. [10.1007/s11047-009-9154-8]
Trace monoids with idempotent generators and measure-only quantum automata
A. Bertoni
;C. MereghettiSecondo
;B. PalanoUltimo
2010
Abstract
In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed ($\MON$-1qfa). The automaton works on a compatibility alphabet $(\Sigma, E)$ of observables and its probabilistic behavior is a formal series on the free partially commutative monoid $\FI(\Sigma, E)$ with idempotent generators. We prove some properties of this class of formal series and we apply the results to analyze the class $\LMO(\Sigma, E)$ of languages recognized by $\MON$-1qfa's with isolated cut point. In particular, we prove that $\LMO(\Sigma, E)$ is a boolean algebra of recognizable languages with finite variation, and that $\LMO(\Sigma, E)$ is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
363.12 kB
Formato
Adobe PDF
|
363.12 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.