Physics – Quantum Physics
Scientific paper
2011-12-13
Physics
Quantum Physics
Comments are welcome
Scientific paper
{\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over {\it two-way probabilistic finite automata} (2PFA) for recognizing some non-regular languages such as the language $L_{eq}=\{a^{n}b^{n}\mid n\in \mathbf{N}\}$ and the palindrome language $L_{pal}=\{\omega\in \{a,b\}^*\mid\omega=\omega^R\}$, where $x^R$ is $x$ in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language $L_{m}=\{xcy\mid \Sigma=\{a, b, c\}, x,y\in\{a,b\}^{*},c\in\Sigma, |x|=|y|\}$ that is similar to the middle language $L_{middle}=\{xay\mid x,y\in\Sigma^{*},a\in\Sigma, |x|=|y|\}$. We prove that the language $L_{m}$ can be recognized by 2QCFA with one-sided error in polynomial expected time. Also, we show that $L_{m}$ can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus $L_{m}$ is another witness of the fact that 2QCFA are more powerful than their classical counterparts.
Li Lvzhou
Qiu Daowen
Zheng Shenggen
No associations
LandOfFree
Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-486326