Regular languages accepted by quantum automata

Authors
Bertoni, A Carpentieri, M
Citation
A. Bertoni et M. Carpentieri, Regular languages accepted by quantum automata, INF COMPUT, 165(2), 2001, pp. 174-182
Citations number
39
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION AND COMPUTATION
ISSN journal
08905401 → ACNP
Volume
165
Issue
2
Year of publication
2001
Pages
174 - 182
Database
ISI
SICI code
0890-5401(20010315)165:2<174:RLABQA>2.0.ZU;2-C
Abstract
In this paper we analyze some features of the behaviour of quantum automata . In particular we prove that the class of languages recognized by quantum automata with isolated cut point is the class of reversible regular languag es. As a more general result, we give a bound on the inverse error that imp lies the regularity of the language accepted by a quantum automaton. (C) 20 01 Academic Press.