It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some
neces- sary and some sufficient conditions for a (regular) language to be recog- nizable by a QFA. For a subclass of regular
languages we get a condition which is necessary and sufficient.
Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation
where both arguments are significant.
Research supported by Berkeley Fellowship for Graduate Studies and, in part, NSF Grant CCR-9800024.
Research supported by Grant No.96.0282 from the Latvian Council of Science and European Commission, contract IST-1999-11234.
For the rest of the paper, we will omit “1-way” because this is the only model of QFAs that we consider in this paper. For
other models of QFAs, see [KW 97] and [AW 99].