6533b851fe1ef96bd12a96b8

RESEARCH PRODUCT

Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages

Maksim KravtsevVasilijs KravcevsMarats Golovkins

subject

Discrete mathematicsNested wordIdempotenceQuantum finite automataAutomata theoryComputer Science::Computational ComplexityAlgebraic numberω-automatonCharacterization (mathematics)Computer Science::Formal Languages and Automata TheoryMathematicsAutomaton

description

We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.

yearjournalcountryeditionlanguage
2011-01-01
https://doi.org/10.1007/978-3-642-22993-0_33