3 citations · 3 across the 5 of their papers we have counts for
5 papers
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
Marats Golovkins, Maksim Kravtsev, Vasilijs Kravcevs
We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA).…
On the Solution of Graph Isomorphism by Dynamical Algorithms
Marats Golovkins
In the recent years, several polynomial algorithms of a dynamical nature have been proposed to address the graph isomorphism problem. In this paper we propose a generalization of a…
Probabilistic Reversible Automata and Quantum Automata
Marats Golovkins, Maksim Kravtsev
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic autom…
Quantum Pushdown Automata
Marats Golovkins
Quantum finite automata, as well as quantum pushdown automata (QPA) were first introduced by C. Moore and J. P. Crutchfield. In this paper we introduce the notion of QPA in a non-e…
Quantum finite multitape automata
Andris Ambainis, Richard Bonner, Rusins Freivalds +2
Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. More…