We consider the model of one-way automata with quantum and classical states (qcfas) introduced in [23]. We show, by a direct approach, that qcfas with isolated cut-point accept regular languages only, thus characterizing their computational power. Moreover, we give a size lower bound for qcfas accepting regular languages, and 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 polynomially increasing the size.
On the power of one-way automata with quantum and classical states / M.P. Bianchi, C. Mereghetti, B. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Implementation and Application of Automata / [a cura di] M. Holzer, M. Kutrib. - [s.l] : Springer Verlag, 2014. - ISBN 9783319088457. - pp. 84-97 (( Intervento presentato al 19. convegno International Conference on Implementation and Application of Automata tenutosi a Giessen nel 2014 [10.1007/978-3-319-08846-4_6].
On the power of one-way automata with quantum and classical states
M.P. Bianchi
;C. MereghettiSecondo
;B. PalanoUltimo
2014
Abstract
We consider the model of one-way automata with quantum and classical states (qcfas) introduced in [23]. We show, by a direct approach, that qcfas with isolated cut-point accept regular languages only, thus characterizing their computational power. Moreover, we give a size lower bound for qcfas accepting regular languages, and 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 polynomially increasing the size.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
265.32 kB
Formato
Adobe PDF
|
265.32 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.