Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Quantum Computing: 1-Way Quantum Automata
| |
|
Quantum Computing: 1-Way Quantum Automata
Alberto Bertoni5  , Carlo Mereghetti5 and Beatrice Palano5
| (5) |
Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano, via Comelico 39/41, 20135 Milano, Italy |
Abstract
In this paper we analyze several models of 1-way quantum finite automata, in the light of formal power series theory. In this
general context, we recall two well known constructions, by proving:
| 1. |
Languages generated with isolated cut-point by a class of bounded rational formal series are regular.
|
| 2. |
If a class of formal series is closed under f-complement, Hadamard product and convex linear combination, then the class of
languages generated with isolated cut-point is closed under boolean operations.
|
We introduce a general model of 1-way quantum automata and we compare their behaviors with those of measure-once, measure-many
and reversible 1-way quantum automata.
Keywords formal power series - quantum finite automata
Partially supported by MURST, under the project “Linguaggi formali: teoria ed applicazioni”.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|