Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Algebraic Characterization of the Class of Languages Recognized by Measure Only Quantum Automata

Comin C.

Fundamenta Informaticae

2014

Vol. 134, nr 3/4

335--353

We study a model of one-way quantum automaton where only measurement operations are allowed (MON-1QFA). We give an algebraic characterization of LMO(Σ), showing that the syntactic monoids of the languages in LMO(Σ) are exactly the J-trivial literally idempotent syntactic monoids, where J is the Green’s relation determined by two-sided ideals. We also prove that LMO(Σ) coincides with the literal variety of literally idempotent piecewise testable languages. This allows us to prove the existence of a polynomial-time algorithm for deciding whether a regular language belongs to LMO(Σ).