Quantum versus Probabilistic One-Way Finite Automata with Counter
| Autor: | Maksim Kravtsev, Richard F. Bonner, Rusins Freivalds |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Nested word Computer science Timed automaton Büchi automaton ω-automaton Nondeterministic finite automaton with ε-moves Turing machine symbols.namesake DFA minimization Deterministic automaton Continuous spatial automaton Quantum finite automata Deterministic system (philosophy) Two-way deterministic finite automaton Nondeterministic finite automaton Discrete mathematics Finite-state machine Quantum dot cellular automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Mobile automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Deterministic finite automaton Probabilistic automaton symbols Automata theory Computer Science::Formal Languages and Automata Theory Quantum cellular automaton |
| Zdroj: | SOFSEM 2001: Theory and Practice of Informatics ISBN: 9783540429128 SOFSEM |
| DOI: | 10.1007/3-540-45627-9_15 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|