6533b834fe1ef96bd129cae8

RESEARCH PRODUCT

The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijanis

subject

Discrete mathematicsDeterministic finite automatonDFA minimizationDeterministic automatonProbabilistic automatonBüchi automatonQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonNonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata TheoryMathematics

description

We present a language Ln which is recognizable by a probabilistic finite automaton (PFA) with probability 1 - ? for all ? > 0 with O(log2 n) states, with a deterministic finite automaton (DFA) with O(n) states, but a quantum finite automaton (QFA) needs at least 2?(n/log n) states.

yearjournalcountryeditionlanguage
2002-01-01
https://doi.org/10.1007/3-540-36137-5_21