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. Mereghetti
Secondo
;
B. Palano
Ultimo
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.
Free partially commutative monoids; Quantum automata
Settore INF/01 - Informatica
2010
Article (author)
File in questo prodotto:
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.

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