6533b85dfe1ef96bd12bf216

RESEARCH PRODUCT

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

Marats GolovkinsMaksim KravtsevVasilijs Kravcevs

subject

FOS: Computer and information sciencesQuantum PhysicsFormal Languages and Automata Theory (cs.FL)FOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputer Science::Computational ComplexityQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory

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-06-13
https://dx.doi.org/10.48550/arxiv.1106.2530