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.
Titolo: | Trace monoids with idempotent generators and measure-only quantum automata |
Autori: | MEREGHETTI, CARLO (Secondo) PALANO, BEATRICE SANTA (Ultimo) |
Parole Chiave: | Free partially commutative monoids; Quantum automata |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2010 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/s11047-009-9154-8 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |