{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T03:11:44Z","timestamp":1652929904946},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","funder":[{"name":"JSPS KAKENHI","award":["24500003","24106009","16K00007"],"award-info":[{"award-number":["24500003","24106009","16K00007"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p> We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic [Formula: see text]-counter automata. Then, we show that exact realtime affine counter automata can recognize a family of regular languages with a few states but the states required by realtime deterministic [Formula: see text]-counter automata cannot be bounded. We also show that stateless affine increment-only counter automata can recognize some nonregular languages with one-sided bounded-error. Moreover, we show that a promise problem not solved by two-way quantum finite automata in polynomial time can be solved by Las Vegas affine finite automata. Lastly, we present an affine finite automaton algorithm using a counter cleverly to recognize a language, for which we do not know any bounded-error affine finite automata or two-way quantum finite automata recognizing it. <\/jats:p>","DOI":"10.1142\/s012905412241009x","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T06:59:51Z","timestamp":1650524391000},"page":"349-370","source":"Crossref","is-referenced-by-count":0,"title":["Exact Affine Counter Automata"],"prefix":"10.1142","volume":"33","author":[{"given":"Masaki","family":"Nakanishi","sequence":"first","affiliation":[{"name":"Department of Education, Art and Science, Yamagata University, Yamagata, 990\u20138560, Japan"}]},{"given":"Kamil","family":"Khadiev","sequence":"additional","affiliation":[{"name":"Kazan Federal University, Kremlevskaya str. 18, Kazan, Russia, Kazan E. K. Zavoisky Physical-Technical Institute, 10\/7, Sibirsky tract, Kazan, Russia"}]},{"given":"Krisjanis","family":"Prusis","sequence":"additional","affiliation":[{"name":"University of Latvia, Faculty of Computing, Center for Quantum Computer Science, R\u0131\u0304ga, Latvia"}]},{"given":"Jevgenijs","family":"Vihrovs","sequence":"additional","affiliation":[{"name":"University of Latvia, Faculty of Computing, Center for Quantum Computer Science, R\u0131\u0304ga, Latvia"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[{"name":"University of Latvia, Faculty of Computing, Center for Quantum Computer Science, R\u0131\u0304ga, Latvia"},{"name":"University of Turku, The Department of Mathematics and Statistics, Turku, Finland"}]}],"member":"219","published-online":{"date-parts":[[2022,4,20]]},"reference":[{"key":"S012905412241009XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90004-9"},{"key":"S012905412241009XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_11"},{"key":"S012905412241009XBIB005","first-page":"117","volume-title":"Annual Symposium on Theoretical Aspects of Computer Science","author":"\u010euri\u0161 P.","year":"1997"},{"key":"S012905412241009XBIB006","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146599"},{"issue":"2","key":"S012905412241009XBIB007","first-page":"157","volume":"17","author":"Geffert V.","year":"2015","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"S012905412241009XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"S012905412241009XBIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53733-7_30"},{"key":"S012905412241009XBIB010","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2003007"},{"key":"S012905412241009XBIB011","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3040"},{"key":"S012905412241009XBIB012","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2012-674"},{"key":"S012905412241009XBIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054121500246"},{"key":"S012905412241009XBIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-87993-8_6"},{"key":"S012905412241009XBIB016","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335396"},{"key":"S012905412241009XBIB017","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.252.20"},{"key":"S012905412241009XBIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22360-5_19"},{"key":"S012905412241009XBIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08846-4_24"},{"issue":"182","key":"S012905412241009XBIB020","volume":"26","author":"Remscrim Z.","year":"2019","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"S012905412241009XBIB021","doi-asserted-by":"publisher","DOI":"10.1147\/rd.105.0388"},{"key":"S012905412241009XBIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411250013X"},{"key":"S012905412241009XBIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13350-8_16"},{"key":"S012905412241009XBIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41312-9_10"},{"key":"S012905412241009XBIB025","first-page":"209","volume-title":"Third Workshop on Non-Classical Models for Automata and Applications \u2014 NCMA 2011","volume":"282","author":"Yakary\u0131lmaz A.","year":"2011"},{"key":"S012905412241009XBIB026","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2012018"},{"key":"S012905412241009XBIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13523-1_18"},{"key":"S012905412241009XBIB028","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-011-9270-0"},{"issue":"2","key":"S012905412241009XBIB029","first-page":"19","volume":"12","author":"Yakary\u0131lmaz A.","year":"2010","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"S012905412241009XBIB030","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2013-803"},{"key":"S012905412241009XBIB031","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90108-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412241009X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T02:57:25Z","timestamp":1652929045000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412241009X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":28,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1142\/S012905412241009X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412241009x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}