{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T09:26:58Z","timestamp":1674898018294},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p> 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<jats:sub>eq<\/jats:sub> = {a<jats:sup>n<\/jats:sup>b<jats:sup>n<\/jats:sup> \u2223 n \u2208 N} and the palindrome language L<jats:sub>pal<\/jats:sub> = {w \u2208 {a,b}* \u2223 w=w<jats:sup>R<\/jats:sup>}, where x<jats:sup>R<\/jats:sup> 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<jats:sub>m<\/jats:sub> = {xcy \u2223 \u2211 = {a,b,c},x,y \u2208 {a,b}*, \u2223x\u2223 = \u2223y\u2223} that is similar to the middle language L<jats:sub>middle<\/jats:sub> = {xay \u2223 x,y \u2208 {a,b}*, \u2223x\u2223 = \u2223y\u2223}. We prove that the language L<jats:sub>m<\/jats:sub> show that L<jats:sub>m<\/jats:sub> can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus L<jats:sub>m<\/jats:sub> is another witness of the fact that 2QCFA are more powerful than their classical counterparts. <\/jats:p>","DOI":"10.1142\/s0129054112500141","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T04:07:23Z","timestamp":1349150843000},"page":"1117-1129","source":"Crossref","is-referenced-by-count":7,"title":["SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES"],"prefix":"10.1142","volume":"23","author":[{"given":"SHENGGEN","family":"ZHENG","sequence":"first","affiliation":[{"name":"Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, P. R. China"}]},{"given":"DAOWEN","family":"QIU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, P. R. China"},{"name":"SQIG\u2013Instituto de Telecomunica\u00e7\u00e3es, Departamento de Matem\u00e1tica, Instituto Superior T\u00e9cnico, TULisbon, Av. Rovisco Pais 1049-001, Lisbon, Portugal"},{"name":"The State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, P. R. China"}]},{"given":"LVZHOU","family":"LI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2012,10,2]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1263-x"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00138-X"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799353443"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0219069"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146599"},{"key":"rf7","doi-asserted-by":"crossref","DOI":"10.1063\/1.3034322","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller W.","year":"1967"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90045-0"},{"key":"rf11","volume-title":"Quantum Computing","author":"Gruska J.","year":"1999"},{"key":"rf12","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.03.021"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.026"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00191-1"},{"key":"rf18","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M. A.","year":"2000"},{"key":"rf19","volume-title":"Introduction to Probabilistic Automata","author":"Paz A.","year":"1971"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-008-0022-y"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.040"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.029"},{"key":"rf25","first-page":"19","volume":"12","author":"Yakaryilmaz A.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.01.008"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1007\/s10773-010-0582-0"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112500141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:17:54Z","timestamp":1565079474000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112500141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":21,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,10,2]]},"published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1142\/S0129054112500141"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112500141","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]}}}