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 - 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.
Titolo: | On the power of one-way automata with quantum and classical states |
Autori: | MEREGHETTI, CARLO (Secondo) PALANO, BEATRICE SANTA (Ultimo) |
Parole Chiave: | descriptional complexity; quantum automata; regular languages |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2014 |
Enti collegati al convegno: | Universitat Giessen |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-319-08846-4_6 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |