6533b855fe1ef96bd12b0661

RESEARCH PRODUCT

Probabilistic Reversible Automata and Quantum Automata

Marats GolovkinsMaksim Kravtsev

subject

Discrete mathematicsProbabilistic finite automataNested wordComputer scienceTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesMobile automatonAutomatonStochastic cellular automatonDeterministic finite automatonDFA minimizationContinuous spatial automatonAutomata theoryQuantum finite automataNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton

description

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.

yearjournalcountryeditionlanguage
2002-01-01
https://doi.org/10.1007/3-540-45655-4_61