Algebraic characterization of the class of languages recognized by measure only quantum automata
From MaRDI portal
Publication:5259269
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.
Recommendations
- Trace monoids with idempotent generators and measure-only quantum automata
- Some algebraic properties of measure-once two-way quantum finite automata
- Quantum finite automata and probabilistic reversible automata: \(\mathcal{R}\)-trivial idempotent languages
- Algebraic results on quantum automata
- Characterizations of 1-Way Quantum Finite Automata
Cited in
(5)- Some algebraic properties of measure-once two-way quantum finite automata
- Trace monoids with idempotent generators and measure-only quantum automata
- Quantum finite automata and probabilistic reversible automata: \(\mathcal{R}\)-trivial idempotent languages
- Quantum finite automata: advances on Bertoni's ideas
- scientific article; zbMATH DE number 6533717 (Why is no real title available?)
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)
