%0 Generic %1 zheng2011languages %A Zheng, Shenggen %A Qiu, Daowen %A Li, Lvzhou %D 2011 %K myown %T Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States %U http://arxiv.org/abs/1112.2844 %X 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 two-way probabilistic finite automata (2PFA) for recognizing some non-regular languages such as the language $L_eq=\a^nb^nnN\$ and the palindrome language $L_pal=\ømega\a,b\^*\midømega=ømega^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\Sigma=\a, b, c\, x,yın\a,b\^*,cın\Sigma, |x|=|y|\$ that is similar to the middle language $L_middle=\xay\mid x,yın\Sigma^*,aın\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.

@misc{zheng2011languages, abstract = {{\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.}, added-at = {2014-01-28T21:45:20.000+0100}, author = {Zheng, Shenggen and Qiu, Daowen and Li, Lvzhou}, biburl = {https://www.bibsonomy.org/bibtex/29bf6b8f195a2308035ed8c7e7eb61d10/shenggenzheng}, description = {Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States}, interhash = {3c84932759e028617007b0728243dfff}, intrahash = {9bf6b8f195a2308035ed8c7e7eb61d10}, keywords = {myown}, note = {cite arxiv:1112.2844Comment: Comments are welcome}, timestamp = {2014-01-28T21:45:20.000+0100}, title = {Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States}, url = {http://arxiv.org/abs/1112.2844}, year = 2011 }