{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:14Z","timestamp":1740133934348,"version":"3.37.3"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","funder":[{"name":"Innovative information technologies","award":["AAP2016\/B032"],"award-info":[{"award-number":["AAP2016\/B032"]}]},{"name":"For development of scientific activity of Faculty of Computing","award":["ZD2018\/20546"],"award-info":[{"award-number":["ZD2018\/20546"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p>We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.<\/jats:p>","DOI":"10.1142\/s012905411950028x","type":"journal-article","created":{"date-parts":[[2019,12,13]],"date-time":"2019-12-13T07:01:30Z","timestamp":1576220490000},"page":"1317-1333","source":"Crossref","is-referenced-by-count":0,"title":["Uncountable Realtime Probabilistic Classes"],"prefix":"10.1142","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4225-7889","authenticated-orcid":false,"given":"Maksims","family":"Dimitrijevs","sequence":"first","affiliation":[{"name":"Center for Quantum Computer Science, Faculty of Computing, University of Latvia, Rai\u0146a bulv\u0101ris 19, R\u0131\u0304ga, LV-1586, Latvia"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[{"name":"Center for Quantum Computer Science, Faculty of Computing, University of Latvia, Rai\u0146a bulv\u0101ris 19, R\u0131\u0304ga, LV-1586, Latvia"}]}],"member":"219","published-online":{"date-parts":[[2019,12,12]]},"reference":[{"key":"S012905411950028XBIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293639"},{"key":"S012905411950028XBIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054116400098"},{"key":"S012905411950028XBIB003","doi-asserted-by":"crossref","unstructured":"K. Chandrasekharan, Chebyshev\u2019s Theorem on the Distribution of Prime Numbers, Introduction to Analytic Number Theory (Springer, 1968), pp. 63\u201383.","DOI":"10.1007\/978-3-642-46124-8_7"},{"key":"S012905411950028XBIB004","first-page":"131","volume-title":"Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016)","volume":"321","author":"Dimitrijevs M.","year":"2016"},{"key":"S012905411950028XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_8"},{"key":"S012905411950028XBIB006","first-page":"65","volume-title":"Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018)","volume":"332","author":"Dimitrijevs M.","year":"2018"},{"key":"S012905411950028XBIB008","doi-asserted-by":"publisher","DOI":"10.1137\/0219069"},{"key":"S012905411950028XBIB009","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10856-4_72"},{"key":"S012905411950028XBIB010","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_101"},{"key":"S012905411950028XBIB011","first-page":"39","volume":"24","author":"Freivalds R.","year":"1985","journal-title":"Ann. Discr. Math."},{"key":"S012905411950028XBIB012","first-page":"287","volume-title":"FCT\u201991","author":"Ka\u0146eps J.","year":"1991"},{"key":"S012905411950028XBIB013","series-title":"LNCS","first-page":"187","volume-title":"RANDOM","volume":"1269","author":"Ka\u0146eps J.","year":"1997"},{"key":"S012905411950028XBIB014","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"volume-title":"Computation: Finite and Infinite Machines","year":"1967","author":"Minsky M.","key":"S012905411950028XBIB015"},{"volume-title":"Introduction to Probabilistic Automata","year":"1971","author":"Paz A.","key":"S012905411950028XBIB016"},{"key":"S012905411950028XBIB017","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"issue":"11","key":"S012905411950028XBIB018","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.26421\/QIC17.11-12-6","volume":"17","author":"Say A. C. C.","year":"2017","journal-title":"Quantum Information and Computation"},{"key":"S012905411950028XBIB019","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-015-9511-8"},{"key":"S012905411950028XBIB020","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58355-6"},{"key":"S012905411950028XBIB021","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113500329"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411950028X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T10:52:07Z","timestamp":1665226327000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411950028X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":20,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S012905411950028X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411950028x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}