Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Dianzi xuebao

Algebraic and Logical Characterizations of Quantum Bchi Automata

Han Zhao-wei

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

The notion of quantum Bchi automaton(LVBA for short)is introduced,by means of quantum state construction, the equivalence of an LVBA and an LVSBA with crisp transition function is proved,based on this,the algebraic and level characterizations and also the Bchi characterization of quantum infinite regular languages are investigated,and also the closed properties of those quantum infinite regular languages under some regular operations are dealt with.By providing the concept of monadic secondorder quantum logic(LVMSO in short),the monadic second-order logic characterizations of infinite regular languages recognized by quantum Biichi automata are presented,which deepen and generalize the fundamental Bchi theorem to quantum setting.

Related papers

Algebraic properties of quantum infinite regular languages

Zhaowei Han

The concepts of quantum Muller automaton and quantum infinite regular language are introduced.In virtue of the fact that the image set of a quantum infinite regular language recognized by an arbitrary quantum Muller automaton is always finite and by means of semantic analysis and quantum state construction, the algebraic characterization of quantum Muller automaton is studied.It is shown that an arbitrary quantum Muller automaton is equivalent to the one which has crisp initial states and transition relation but with quantum final states. Based on this,the algebraic description and the level characterization of quantum infinite regular languages are obtained, and it is proved that an arbitrary quantum infinite language A is recognizable if and only if the image set of A is finite and A can be represented as a finite union of special quantum infinite languages.As applications,it is proved that even if the distributivity law does not hold in quantum logic itself, quantum infinite regular languages are still closed under regular operations.

Journal of Shaanxi Normal University•Jan 1, 2012•0 citations

(Extended Version) Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata

Carlo Comin

We study a model of one-way quantum automaton where only measurement operations are allowed ($\mon$). 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 regular languages. This allows us to prove the existence of a polynomial time algorithm for deciding whether a regular language belongs to $\lmo(Σ)$ and to discuss definability issues in terms of the existential first-order logic $Σ_1[

arXiv:1301.3931•Jan 16, 2013•0 citations

Characterizations of Quantum Automata

Qiu Dao

The relationships among various quantum automata are clarified, and in particular, variously equivalent characterizations of quantum automata are established. The G-quantum automata, g-quantum automata, (generalized) quantum automata, G-quantum grammars and g-quantum grammars are presented, and their connections to some of the other existing quantum automata are expounded. Under a certain condition, the equivalence between the G(g)-quantum automata and G(g)-quantum grammars is discussed. Therefore the problem of quantum grammars generating quantum regular languages is solved. The relation between quantum and regular languages is dealt with, and particularly, two open problems proposed by Gudder are answered. Finally, the method of decreasing the dimensions of spaces of states on quantum automata is given.

•Jan 1, 2003•0 citations

On the class of languages recognizable by 1-way quantum finite automata

Andris Ambainis, Arnolds Ķikusts, Māris Valdats

It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

arXiv:quant-ph/0009004•Sep 1, 2000•6 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•348 citations

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano

Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.

RAIRO - Theoretical Informatics and Applications•Apr 1, 2006•27 citations
The notion of quantum Bchi automaton(LVBA for short)is introduced,by means of quantum state construction, the equivalence of an LVBA and an LVSBA with crisp transition function is proved,based on this,the algebraic and level characterizations and also the Bchi characterization of quantum infinite regular languages are investigated,and also the closed properties of those quantum infinite regular languages under some regular operations are dealt with.By providing the concept of monadic secondorder quantum logic(LVMSO in short),the monadic second-order logic characterizations of infinite regular languages recognized by quantum Biichi automata are presented,which deepen and generalize the fundamental Bchi theorem to quantum setting.
The concepts of quantum Muller automaton and quantum infinite regular language are introduced.In virtue of the fact that the image set of a quantum infinite regular language recognized by an arbitrary quantum Muller automaton is always finite and by means of semantic analysis and quantum state construction, the algebraic characterization of quantum Muller automaton is studied.It is shown that an arbitrary quantum Muller automaton is equivalent to the one which has crisp initial states and transition relation but with quantum final states. Based on this,the algebraic description and the level characterization of quantum infinite regular languages are obtained, and it is proved that an arbitrary quantum infinite language A is recognizable if and only if the image set of A is finite and A can be represented as a finite union of special quantum infinite languages.As applications,it is proved that even if the distributivity law does not hold in quantum logic itself, quantum infinite regular languages are still closed under regular operations.
We study a model of one-way quantum automaton where only measurement operations are allowed ($\mon$). We give an algebraic characterization of $\lmo(Σ)$, showing that the syntactic monoids of the languages in $\lmo(Σ)$ are exactly the JJJ-trivial literally idempotent syntactic monoids, where JJJ 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(Σ)$ and to discuss definability issues in terms of the existential first-order logic $Σ_1[
The relationships among various quantum automata are clarified, and in particular, variously equivalent characterizations of quantum automata are established. The G-quantum automata, g-quantum automata, (generalized) quantum automata, G-quantum grammars and g-quantum grammars are presented, and their connections to some of the other existing quantum automata are expounded. Under a certain condition, the equivalence between the G(g)-quantum automata and G(g)-quantum grammars is discussed. Therefore the problem of quantum grammars generating quantum regular languages is solved. The relation between quantum and regular languages is dealt with, and particularly, two open problems proposed by Gudder are answered. Finally, the method of decreasing the dimensions of spaces of states on quantum automata is given.
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.