We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Trace monoids with idempotent generators and measure-only quantum automata.
- Authors
Bertoni, Alberto; Mereghetti, Carlo; Palano, Beatrice
- Abstract
In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed (-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 $$\hbox{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 $${\bf LMO}(\Sigma, E)$$ of languages recognized by -1qfa’s with isolated cut point. In particular, we prove that $${\bf LMO}(\Sigma, E)$$ is a boolean algebra of recognizable languages with finite variation, and that $${\bf LMO}(\Sigma, E)$$ is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.
- Subjects
MONOIDS; MACHINE theory; QUANTUM theory; AUTOMATION; MATHEMATICS
- Publication
Natural Computing, 2010, Vol 9, Issue 2, p383
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-009-9154-8