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

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

2011-06-13

arxiv.org/abs/1106.2530v1

MFCS 2011, Lecture Notes in Computer Science, Vol. 6907, pp. 351-363, 2011

Computer Science

Formal Languages and Automata Theory

30 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-429983