{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:08:55Z","timestamp":1767236935490,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T00:00:00Z","timestamp":1510012800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002322","name":"CAPES","doi-asserted-by":"crossref","award":["88881.030338\/2013-01"],"award-info":[{"award-number":["88881.030338\/2013-01"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s11047-017-9652-z","type":"journal-article","created":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T01:50:23Z","timestamp":1510019423000},"page":"283-293","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Language recognition power and succinctness of affine automata"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6081-9099","authenticated-orcid":false,"given":"Marcos","family":"Villagra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,7]]},"reference":[{"key":"9652_CR1","doi-asserted-by":"crossref","unstructured":"Ablayev FM, Gainutdinova A, Khadiev K, Yakary\u0131lmaz A (2014) Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: Descriptional complexity of formal systems, LNCS, vol 8614. Springer, pp 53\u201364","DOI":"10.1007\/978-3-319-09704-6_6"},{"key":"9652_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis A, Freivalds R (1998) 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS\u201998. pp 332\u2013341. \n                        ArXiv:9802062","DOI":"10.1109\/SFCS.1998.743469"},{"issue":"7","key":"9652_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.ipl.2012.01.001","volume":"112","author":"A Ambainis","year":"2012","unstructured":"Ambainis A, Yakary\u0131lmaz A (2012) Superiority of exact quantum automata for promise problems. Inf Process Lett 112(7):289\u2013291","journal-title":"Inf Process Lett"},{"key":"9652_CR4","unstructured":"Ambainis A, Yakary\u0131lmaz A (2015) Automata and quantum computing. Tech. Rep. \n                        ArXiv:1507.01988"},{"key":"9652_CR5","unstructured":"Belovs A, Montoya J A, Yakary\u0131lmaz A (2016) Can one quantum bit separate any pair of words with zero-error? Tech. Rep. \n                        ArXiv:1602.07967"},{"key":"9652_CR6","doi-asserted-by":"crossref","unstructured":"D\u00edaz-Caro A, Yakary\u0131lmaz A (2016) Affine computation and affine automaton. In: Computer science\u2014theory and applications, LNCS, vol 9691. Springer, pp 1\u201315. \n                        ArXiv:1602.04732","DOI":"10.1007\/978-3-319-34171-2_11"},{"key":"9652_CR7","doi-asserted-by":"crossref","unstructured":"Freivalds R, Karpinski M (1994) Lower space bounds for randomized computation. In: ICALP\u201994. pp 580\u2013592","DOI":"10.1007\/3-540-58201-0_100"},{"key":"9652_CR8","doi-asserted-by":"crossref","unstructured":"Gainutdinova A, Yakary\u0131lmaz A (2015) Unary probabilistic and quantum automata on promise problems. In: Developments in language theory, LNCS, vol 9168. Springer, pp 252\u2013263","DOI":"10.1007\/978-3-319-21500-6_20"},{"issue":"2","key":"9652_CR9","first-page":"157","volume":"17","author":"V Geffert","year":"2015","unstructured":"Geffert V, Yakary\u0131lmaz A (2015) Classical automata on promise problems. Discrete Math Theor Comput Sci 17(2):157\u2013180","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"3","key":"9652_CR10","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1142\/S0129054115500215","volume":"26","author":"J Gruska","year":"2015","unstructured":"Gruska J, Qiu D, Zheng S (2015) Potential of quantum finite automata with exact acceptance. Int J Found Comput Sci 26(3):381\u2013398","journal-title":"Int J Found Comput Sci"},{"issue":"1","key":"9652_CR11","doi-asserted-by":"crossref","first-page":"70","DOI":"10.4018\/jncr.2010010104","volume":"1","author":"M Hirvensalo","year":"2010","unstructured":"Hirvensalo M (2010) Quantum automata with open time evolution. Int J Nat Comput 1(1):70\u201385","journal-title":"Int J Nat Comput"},{"key":"9652_CR12","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/978-3-319-53733-7_30","volume":"10168","author":"M Hirvensalo","year":"2017","unstructured":"Hirvensalo M, Moutot E, Yakary\u0131lmaz A (2017) On the computational power of affine automata. Lang Automat Theory Appl Lect Notes Comput Sci 10168:405\u2013417","journal-title":"Lang Automat Theory Appl Lect Notes Comput Sci"},{"key":"9652_CR13","unstructured":"Ibrahimov R, Khadiev K, Pr\u016bsis K, Yakary\u0131lmaz A (2017) Zero-error affine, unitary, and probabilistic OBDDs. Tech. Rep. \n                        ArXiv:1703.07184"},{"key":"9652_CR14","unstructured":"Kupferman O, Ta-Shma A, Vardi M Y (1999) Counting with automata. In: Short paper presented at the 15th annual IEEE symposium on logic in computer science (LICS 2000)"},{"key":"9652_CR15","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.tcs.2011.10.021","volume":"419","author":"L Li","year":"2012","unstructured":"Li L, Qiu D, Zou X, Li L, Wu L, Mateus P (2012) Characterizations of one-way general quantum finite automata. Theor Comput Sci 419:73\u201391","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9652_CR16","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/S0097539793253851","volume":"27","author":"II Macarie","year":"1998","unstructured":"Macarie II (1998) Space-efficient deterministic simulation of probabilistic automata. SIAM J Comput 27(2):448\u2013465","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"9652_CR17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C Moore","year":"2000","unstructured":"Moore C, Crutchfield JP (2000) Quantum automata and quantum grammars. Theor Comput Sci 237(1\u20132):275\u2013306","journal-title":"Theor Comput Sci"},{"key":"9652_CR18","unstructured":"Nakanishi M, Khadiev K, Pr\u016bsis K, Vihrovs J, Yakary\u0131lmaz A (2017) Affine counter automata. In: Proceedings 15th international conference on automata and formal languages, EPTCS, vol 252. pp 205\u2013218"},{"key":"9652_CR19","volume-title":"Introduction to probabilistic automata","author":"A Paz","year":"1971","unstructured":"Paz A (1971) Introduction to probabilistic automata. Academic Press, New York"},{"key":"9652_CR20","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M Rabin","year":"1959","unstructured":"Rabin M, Scott D (1959) Finite automata and their decision problems. IBM J Res Dev 3:114\u2013125","journal-title":"IBM J Res Dev"},{"key":"9652_CR21","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"MO Rabin","year":"1963","unstructured":"Rabin MO (1963) Probabilistic automata. Inf Control 6:230\u2013243","journal-title":"Inf Control"},{"key":"9652_CR22","doi-asserted-by":"crossref","unstructured":"Rashid J, Yakary\u0131lmaz A (2014) Implications of quantum automata for contextuality. In: Implementation and application of automata, LNCS, vol 8587. Springer, pp 318\u2013331. \n                        ArXiv:1404.2761","DOI":"10.1007\/978-3-319-08846-4_24"},{"key":"9652_CR23","doi-asserted-by":"crossref","unstructured":"Say ACC, Yakary\u0131lmaz A (2014) Quantum finite automata: A modern introduction. In: Computing with new resources, LNCS, vol 8808. Springer, pp 208\u2013222","DOI":"10.1007\/978-3-319-13350-8_16"},{"issue":"1","key":"9652_CR24","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s11047-015-9511-8","volume":"15","author":"AM Shur","year":"2016","unstructured":"Shur AM, Yakary\u0131lmaz A (2016) More on quantum, stochastic, and pseudo stochastic languages with few states. Nat Comput 15(1):129\u2013141","journal-title":"Nat Comput"},{"key":"9652_CR25","doi-asserted-by":"crossref","first-page":"27","DOI":"10.5186\/aasfm.1975.0126","volume":"1","author":"P Turakainenn","year":"1975","unstructured":"Turakainenn P (1975) Word-functions of stochastic and pseudo stochastic automata. Ann Acad Sci Fenn Ser A I Math 1:27\u201337","journal-title":"Ann Acad Sci Fenn Ser A I Math"},{"key":"9652_CR26","unstructured":"Villagra M, Yakary\u0131lmaz A (2016) Language recognition power and succintness of affine automata. In: Unconventional computation and natural computation, LNCS, vol. 9726. Springer, pp 116\u2013129"},{"key":"9652_CR27","doi-asserted-by":"crossref","unstructured":"Yakary\u0131lmaz A, Say ACC (2009) Languages recognized with unbounded error by quantum finite automata. In: Computer science\u2014theory and applications, LNCS, vol 5675. Springer, pp 356\u2013367","DOI":"10.1007\/978-3-642-03351-3_33"},{"issue":"9&10","key":"9652_CR28","first-page":"747","volume":"10","author":"A Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz A, Say ACC (2010) Languages recognized by nondeterministic quantum finite automata. Quantum Inf Comput 10(9&10):747\u2013770","journal-title":"Quantum Inf Comput"},{"issue":"2","key":"9652_CR29","first-page":"19","volume":"12","author":"A Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz A, Say ACC (2010) Succinctness of two-way probabilistic and quantum finite automata. Discrete Math Theor Comput Sci 12(2):19\u201340","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"6","key":"9652_CR30","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"279","author":"A Yakary\u0131lmaz","year":"2011","unstructured":"Yakary\u0131lmaz A, Say ACC (2011) Unbounded-error quantum computation with small space bounds. Inf Comput 279(6):873\u2013892","journal-title":"Inf Comput"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-017-9652-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-017-9652-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-017-9652-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T16:26:31Z","timestamp":1526401591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-017-9652-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,7]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["9652"],"URL":"https:\/\/doi.org\/10.1007\/s11047-017-9652-z","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2017,11,7]]}}}