We consider the model of one-way automata with quantum and classical states (QCFAs) introduced in [28]. We show, by a direct approach, that QCFAs with isolated cut-point accept regular languages only, thus characterizing their computational power. Concerning descriptional power, we quickly overview a size lower bound for QCFAs accepting regular languages, and address its optimality. Then, we explicitly build QCFAs accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAs with isolated cut-point, maintaining the same cut-point, isolation, and only polynomially increasing the size.
On the Power of One-Way Automata with Quantum and Classical States / M.P. Bianchi, C. Mereghetti, B. Palano. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 26:7(2015), pp. 895-912. [10.1142/S0129054115400055]
On the Power of One-Way Automata with Quantum and Classical States
M.P. BianchiPrimo
;C. MereghettiSecondo
;B. PalanoUltimo
2015
Abstract
We consider the model of one-way automata with quantum and classical states (QCFAs) introduced in [28]. We show, by a direct approach, that QCFAs with isolated cut-point accept regular languages only, thus characterizing their computational power. Concerning descriptional power, we quickly overview a size lower bound for QCFAs accepting regular languages, and address its optimality. Then, we explicitly build QCFAs accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAs with isolated cut-point, maintaining the same cut-point, isolation, and only polynomially increasing the size.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
458.94 kB
Formato
Adobe PDF
|
458.94 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.