On the power of one-way automata with quantum and classical states

Bianchi, M.P.; Mereghetti, C.; Palano, B.

doi:10.1007/978-3-319-08846-4_6

IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

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:	BIANCHI, MARIA PAOLA (Corresponding) 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

Pubblicazioni consigliate

Loading suggested articles...

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/2434/249697

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.