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

东华大学学报:英文版

Closure of q-Quantum Languages

莫智文, 郭秀红, 舒兰

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the intersection and union of two different q-quantum languages are also q-quantum languages.

Related papers

Some Properties of Quantum Languages

Guo Xiu-hong

Tensor product of two automata over the different alphabets is defined in this paper and quantum languages accepted by the tensor product are studied. Quantum languages and generalized quantum languages are discussed. Some of their properties are derived.

Journal of Sichuan Normal University•Jan 1, 2005•0 citations

The class of languages recognizable by 1-way quantum finite automata is not closed under union

Māris Valdats

In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.

arXiv:quant-ph/0001005•Jan 4, 2000•8 citations

Some results on equivalence of multi-letter quantum finite automata

Tianrong Lin

Two quantum finite automata are equivalent if for all input string $ω$ over the input alphabet the two automata accept $ω$ with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a $k_1$-letter QFA $\mathcal{A}_1$ and a $k_2$-letter QFA $\mathcal{A}_2$ over $Σ=\{σ\}$, are equivalent if and only if they are $(n_1+n_2)^4+k-1$-equivalent where $n_i$ is the number of states of $\mathcal{A}_i$, $i=1,2$, and $k=\max\{k_1,k_2\}$. In this letter, we improve the above upper-bound to $(n_1^2+n_2^2-1)+k$. This also answers an open problem of Qiu et al. [Acta Informatica 48 (2011) 271-290]. Further, we show that, in the case of $Σ=\{σ_1,...,σ_t\}$ with $2\leq t<\infty$, there exists an integer $z$ such that $\mathcal{A}_1$ and $\mathcal{A}_2$ are equivalent if and only if they satisfy $z$-equivalent.

arXiv:1106.5223•Jun 26, 2011•0 citations

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

Tianrong Lin

We first show that given a $k_1$-letter quantum finite automata $\mathcal{A}_1$ and a $k_2$-letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $Σ$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)$ where $0<λ\leq 1$ and $\mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.

arXiv:1203.0113•Mar 1, 2012•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 equivalence and emptiness problems of multi-letter (measure many) quantum finite automata

Tianrong Lin

In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a $k_1$-letter quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter quantum finite automaton $\mathcal{A}_2$ over the same input alphabet $\Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the number of states in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the number of states in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a $k$-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a $k$-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a $k$-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.

•Mar 1, 2012•0 citations
Two quantum finite automata are equivalent if for all input string ωωω over the input alphabet the two automata accept ωωω with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a k1k_1k1​-letter QFA A1\mathcal{A}_1A1​ and a k2k_2k2​-letter QFA A2\mathcal{A}_2A2​ over Σ={σ}Σ=\{σ\}Σ={σ}, are equivalent if and only if they are (n1+n2)4+k−1(n_1+n_2)^4+k-1(n1​+n2​)4+k−1-equivalent where nin_ini​ is the number of states of Ai\mathcal{A}_iAi​, i=1,2i=1,2i=1,2, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. In this letter, we improve the above upper-bound to (n12+n22−1)+k(n_1^2+n_2^2-1)+k(n12​+n22​−1)+k. This also answers an open problem of Qiu et al. [Acta Informatica 48 (2011) 271-290]. Further, we show that, in the case of Σ={σ1,...,σt}Σ=\{σ_1,...,σ_t\}Σ={σ1​,...,σt​} with 2≤t<∞2\leq t<\infty2≤t<∞, there exists an integer zzz such that A1\mathcal{A}_1A1​ and A2\mathcal{A}_2A2​ are equivalent if and only if they satisfy zzz-equivalent.
We first show that given a k1k_1k1​-letter quantum finite automata A1\mathcal{A}_1A1​ and a k2k_2k2​-letter quantum finite automata A2\mathcal{A}_2A2​ over the same input alphabet ΣΣΣ, they are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|Σ|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where n1n_1n1​, i=1,2i=1,2i=1,2, are the numbers of state in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a k1k_1k1​-letter measure many quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter measure many quantum finite automaton A2\mathcal{A}_2A2​ are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|Σ|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the numbers of state in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for kkk-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether L≥λ(A1)=L≥λ(A2)L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)L≥λ​(A1​)=L≥λ​(A2​) where 0<λ≤10<λ\leq 10<λ≤1 and Ai\mathcal{A}_iAi​ are kik_iki​-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for kkk-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.
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 study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a k1k_1k1​-letter quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter quantum finite automaton A2\mathcal{A}_2A2​ over the same input alphabet Σ\SigmaΣ, they are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the number of states in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a k1k_1k1​-letter measure many quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter measure many quantum finite automaton A2\mathcal{A}_2A2​ are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the number of states in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a kkk-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a kkk-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a kkk-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.