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

DOI10.3233/FI-2014-1105zbMATH Open1322.68073arXiv1206.1702MaRDI QIDQ5259269FDOQ5259269

Carlo Comin

Publication date: 26 June 2015

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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 literal pseudovariety of J-trivial literally idempotent 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 regular languages. This allows us to prove the existence of a polynomial time algorithm for deciding whether a regular language belongs to LMO.

Full work available at URL: https://arxiv.org/abs/1206.1702

zbMATH Keywords

quantum automataquantum measurementssyntactic monoidspiecewise testable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cited In (2)

• Title not available (Why is that?)
• Quantum finite automata: advances on Bertoni's ideas

This page was built for publication: Algebraic Characterization of the Class of Languages Recognized by Measure Only Quantum Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259269)