东华大学学报：英文版

Closure of q-Quantum Languages

莫智文, 郭秀红, 舒兰

Published Jan 1, 2007• 0 citations

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

Closure of q-Quantum Languages

Zhiwen Mo

东华大学学报：英文版Jan 1, 20070 citations

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 UniversityJan 1, 20050 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/0001005Jan 4, 20003 citations

Some results on equivalence of multi-letter quantum finite automata

Tianrong Lin

arXiv:1106.5223Jun 26, 20110 citations

Determining the equivalence for 1-way quantum finite automata

Lvzhou Li, Daowen Qiu

arXiv:quant-ph/0703087Mar 11, 20071 citation

Characterizations of Quantum Automata

Qiu Dao

Jan 1, 20030 citations

东华大学学报：英文版

Closure of q-Quantum Languages

莫智文, 郭秀红, 舒兰

Published Jan 1, 2007• 0 citations

OpenAlex

Abstract

Related papers

Closure of q-Quantum Languages

Zhiwen Mo

东华大学学报：英文版Jan 1, 20070 citations

Some Properties of Quantum Languages

Guo Xiu-hong

Journal of Sichuan Normal UniversityJan 1, 20050 citations

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

Māris Valdats

arXiv:quant-ph/0001005Jan 4, 20003 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.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.5223Jun 26, 20110 citations

Determining the equivalence for 1-way quantum finite automata

Lvzhou Li, Daowen Qiu

In this paper, we focus on determining the equivalence for {\it 1-way quantum finite automata with control language} (CL-1QFAs) defined by Bertoni et al and {\it measure-many 1-way quantum finite automata} (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: \begin{enumerate} \item[(i)] Two CL-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with control languages (regular languages) ${\cal L}_1$ and ${\cal L}_2$ , respectively, are equivalent if and only if they are $(c_1n_1^2+c_2n_2^2-1)$ -equivalent. Furthermore, if ${\cal L}_1$ and ${\cal L}_2$ are given in the form of DFAs, with $m_1$ and $m_2$ states, respectively, then there exists a polynomial-time algorithm running in time $O ((m_1n_1^2+m_2n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether they are equivalent. \item[(ii)] Two MM-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with $n_1$ and $n_2$ states, respectively, are equivalent if and only if they are $(3n_1^2+3n_2^2-1)$ -equivalent. Furthermore, there is a polynomial-time algorithm running in time $O ((3n_1^2+3n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether ${\cal A}_1$ and ${\cal A}_2$ are equivalent.In this paper, we focus on determining the equivalence for {\it 1-way quantum finite automata with control language} (CL-1QFAs) defined by Bertoni et al and {\it measure-many 1-way quantum finite automata} (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: \begin{enumerate} \item[(i)] Two CL-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with control languages (regular languages) ${\cal L}_1$ and ${\cal L}_2$, respectively, are equivalent if and only if they are $(c_1n_1^2+c_2n_2^2-1)$-equivalent. Furthermore, if ${\cal L}_1$ and ${\cal L}_2$ are given in the form of DFAs, with $m_1$ and $m_2$ states, respectively, then there exists a polynomial-time algorithm running in time $O ((m_1n_1^2+m_2n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether they are equivalent. \item[(ii)] Two MM-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with $n_1$ and $n_2$ states, respectively, are equivalent if and only if they are $(3n_1^2+3n_2^2-1)$-equivalent. Furthermore, there is a polynomial-time algorithm running in time $O ((3n_1^2+3n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether ${\cal A}_1$ and ${\cal A}_2$ are equivalent.

arXiv:quant-ph/0703087Mar 11, 20071 citation

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.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, 20030 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

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.

{\cal A}_1

and

{\cal A}_2

with control languages (regular languages)

{\cal L}_1

and

{\cal L}_2

, respectively, are equivalent if and only if they are

(c_1n_1^2+c_2n_2^2-1)

-equivalent. Furthermore, if

{\cal L}_1

and

{\cal L}_2

are given in the form of DFAs, with

m_1

and

m_2

states, respectively, then there exists a polynomial-time algorithm running in time

O ((m_1n_1^2+m_2n_2^2)^4)

that takes as input

{\cal A}_1

and

{\cal A}_2

and determines whether they are equivalent. \item[(ii)] Two MM-1QFAs

{\cal A}_1

and

{\cal A}_2

with

n_1

and

n_2

states, respectively, are equivalent if and only if they are

(3n_1^2+3n_2^2-1)

-equivalent. Furthermore, there is a polynomial-time algorithm running in time

O ((3n_1^2+3n_2^2)^4)

that takes as input

{\cal A}_1

and

{\cal A}_2

and determines whether

{\cal A}_1

and

{\cal A}_2

are equivalent.