6533b7d7fe1ef96bd12678ce

RESEARCH PRODUCT

Quantum Finite One-Counter Automata

Maksim Kravtsev

subject

Nested wordTheoretical computer scienceFinite-state machineComputer scienceω-automatonAutomatonMobile automatonDeterministic finite automatonDeterministic automatonContinuous spatial automatonProbabilistic automatonQuantum finite automataAutomata theoryNondeterministic finite automatonQuantum cellular automaton

description

In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. The well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. That allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. The recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.

yearjournalcountryeditionlanguage
1999-01-01
https://doi.org/10.1007/3-540-47849-3_31