{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T05:29:56Z","timestamp":1687584596120},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,8]]},"abstract":"The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.<\/jats:p>","DOI":"10.1142\/s012905411250013x","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T08:07:23Z","timestamp":1349165243000},"page":"1099-1116","source":"Crossref","is-referenced-by-count":6,"title":["QUANTUM COUNTER AUTOMATA"],"prefix":"10.1142","volume":"23","author":[{"given":"A. C.","family":"CEM SAY","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Bo\u011fazi\u00e7i University, Bebek 34342 \u0130stanbul, Turkey"}]},{"given":"ABUZER","family":"YAKARYILMAZ","sequence":"additional","affiliation":[{"name":"Faculty of Computing, University of Latvia, Raina bulv. 19, Riga, LV-1586, Latvia"}]}],"member":"219","published-online":{"date-parts":[[2012,10,2]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1067-1"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/0219069"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.4018\/jncr.2010010104"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.11.001"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1314-y"},{"key":"rf8","first-page":"405","volume":"1","author":"Kaneps J\u0101nis","journal-title":"Discrete Mathematics and Applications"},{"key":"rf11","first-page":"1120","volume":"89","author":"Nakanishi Masaki","journal-title":"IEICE Transactions E"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90373-1"},{"key":"rf13","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen Michael A.","year":"2000"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/193820.193835"},{"key":"rf15","volume":"1","author":"Rabin Michael O.","journal-title":"Israel Journal of Mathematics"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0177-8"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"747","DOI":"10.26421\/QIC10.9-10-3","volume":"10","author":"Yakary\u0131lmaz Abuzer","journal-title":"Quantum Information and Computation"},{"key":"rf21","first-page":"19","volume":"12","author":"Yakary\u0131lmaz Abuzer","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.01.008"},{"key":"rf23","author":"Yakary\u0131lmaz Abuzer","journal-title":"Natural Computing"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.034"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00412-1"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411250013X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T22:08:44Z","timestamp":1643494124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411250013X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2012,10,2]]},"published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1142\/S012905411250013X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411250013x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]}}}