To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic
reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible
models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way
automata.
Research partially supported by the Latvian Council of Science, grant No. 01.0354 and grant for Ph.D. students; University
of Latvia, K. Morbergs grant; European Commission, contract IST-1999-11234
Research partially supported by the Latvian Council of Science, grant No. 01.0354 and European Commission, contract IST-1999-11234