6533b874fe1ef96bd12d607b

RESEARCH PRODUCT

Quantum versus Probabilistic One-Way Finite Automata with Counter

Maksim KravtsevRichard F. BonnerRusins Freivalds

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordComputer scienceTimed automatonBüchi automatonω-automatonNondeterministic finite automaton with ε-movesTuring machinesymbols.namesakeDFA minimizationDeterministic automatonContinuous spatial automatonQuantum finite automataDeterministic system (philosophy)Two-way deterministic finite automatonNondeterministic finite automatonDiscrete mathematicsFinite-state machineQuantum dot cellular automatonNonlinear Sciences::Cellular Automata and Lattice GasesMobile automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonProbabilistic automatonsymbolsAutomata theoryComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton

description

The paper adds the one-counter one-way finite automaton [6] to the list of classical computing devices having quantum counterparts more powerful in some cases. Specifically, two languages are considered, the first is not recognizable by deterministic one-counter one-way finite automata, the second is not recognizable with bounded error by probabilistic one-counter one-way finite automata, but each recognizable with bounded error by a quantum one-counter one-way finite automaton. This result contrasts the case of one-way finite automata without counter, where it is known [5] that the quantum device is actually less powerful than its classical counterpart.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-45627-9_15