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. Mereghetti
Secondo
;
B. Palano
Ultimo
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.
descriptional complexity; quantum automata; regular languages
Settore INF/01 - Informatica
Universitat Giessen
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/249697
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact