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

Issue title: Theoretical Computer Science

Article type: Research Article

Authors: Comin, Carlo

Affiliations: Dipartimento di Informatica, Universitá degli Studi di Milano, via Comelico 39/41, Milano, Italy. [email protected]

Note: [] The author wish to thank Prof. Alberto Bertoni for having introduced him to the problem and for the stimulating discussions and research directions that finally lead to the results of this paper, Dr. Maria-Paola Bianchi for the kind collaboration on the structural drawing-up of the article. Also wish to thank the anonymous referees for their careful review and for their valuable comments, which improved both the content and quality of the manuscript. Address for correspondence: Dipartimento di Informatica, Universitá degli Studi di Milano, via Comelico 39/41, Milano, Italy

Abstract: 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(Σ).

Keywords: quantum automata, quantum measurements, syntactic monoids, piecewise testable languages

DOI: 10.3233/FI-2014-1105

Journal: Fundamenta Informaticae, vol. 134, no. 3-4, pp. 335-353, 2014