{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T22:54:34Z","timestamp":1785884074385,"version":"3.56.0"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p> In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero weight acceptance. We show that the universality problem is undecidable for three-state automata by a direct reduction from the infinite Post correspondence problem. We also consider other more general acceptance conditions as well as their complements with respect to the universality and the emptiness problems. Additionally, we build a universal integer weighted automaton with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system. <\/jats:p>","DOI":"10.1142\/s0129054122440014","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T11:04:17Z","timestamp":1667214257000},"page":"163-182","source":"Crossref","is-referenced-by-count":1,"title":["Integer Weighted Automata on Infinite Words"],"prefix":"10.1142","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3633-4902","authenticated-orcid":false,"given":"Vesa","family":"Halava","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Turku, Turku, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9640-6309","authenticated-orcid":false,"given":"Tero","family":"Harju","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Turku, Turku, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2210-1481","authenticated-orcid":false,"given":"Reino","family":"Niskanen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Mathematics, Liverpool John Moores University, Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7192-7853","authenticated-orcid":false,"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"S0129054122440014BIB001","doi-asserted-by":"crossref","first-page":"104651","DOI":"10.1016\/j.ic.2020.104651","volume":"282","author":"Almagor S.","year":"2020","journal-title":"Inf. Comput."},{"key":"S0129054122440014BIB002","series-title":"LIPIcs","first-page":"14:1","volume-title":"Proc. CONCUR 2018","volume":"118","author":"Blondin M.","year":"2018"},{"key":"S0129054122440014BIB003","first-page":"3","volume-title":"Proc. RP 2021, LNCS","volume":"13035","author":"Boker U.","year":"2021"},{"issue":"4","key":"S0129054122440014BIB004","doi-asserted-by":"crossref","DOI":"10.1145\/1805950.1805953","volume":"11","author":"Chatterjee K.","year":"2010","journal-title":"ACM Trans. Comput. Log."},{"issue":"3","key":"S0129054122440014BIB005","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0097-8493(93)90079-O","volume":"17","author":"Culik K.","year":"1993","journal-title":"Comput. Graph."},{"issue":"3","key":"S0129054122440014BIB006","first-page":"451","volume":"46","author":"Dong J.","year":"2012","journal-title":"ITA"},{"key":"S0129054122440014BIB007","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted Automata","author":"Droste M.","year":"2009"},{"issue":"1","key":"S0129054122440014BIB009","doi-asserted-by":"crossref","first-page":"189","DOI":"10.3233\/FI-1999-381215","volume":"38","author":"Halava V.","year":"1999","journal-title":"Fundam. Inform."},{"issue":"4","key":"S0129054122440014BIB010","first-page":"551","volume":"40","author":"Halava V.","year":"2006","journal-title":"RAIRO \u2014 ITA"},{"key":"S0129054122440014BIB011","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.ic.2017.05.001","volume":"255","author":"Halava V.","year":"2017","journal-title":"Inf. Comput."},{"key":"S0129054122440014BIB012","series-title":"LNCS","first-page":"167","volume-title":"Proc. DLT 2021","volume":"12811","author":"Halava V.","year":"2021"},{"issue":"1","key":"S0129054122440014BIB013","doi-asserted-by":"crossref","first-page":"177","DOI":"10.3233\/FI-2017-1559","volume":"154","author":"Halava V.","year":"2017","journal-title":"Fundam. Inform."},{"issue":"1","key":"S0129054122440014BIB014","volume":"9","author":"Kiefer S.","year":"2013","journal-title":"LMCS"},{"issue":"1","key":"S0129054122440014BIB015","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.tcs.2004.09.016","volume":"330","author":"Matiyasevich Yu.","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"S0129054122440014BIB016","volume-title":"Computation: Finite and infinite machines","author":"Minsky M. L.","year":"1967"},{"key":"S0129054122440014BIB017","series-title":"LIPIcs","first-page":"649","volume-title":"STACS 2015","volume":"30","author":"Neary T.","year":"2015"},{"key":"S0129054122440014BIB018","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/j.jcss.2019.08.003","volume":"107","author":"Niskanen R.","year":"2020","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"S0129054122440014BIB019","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"Post E. L.","year":"1946","journal-title":"Bull. Amer. Math. Soc."},{"key":"S0129054122440014BIB020","doi-asserted-by":"crossref","first-page":"431","DOI":"10.7551\/mitpress\/3007.001.0001","volume-title":"Finite-State Language Processing","author":"Roche E.","year":"1997"},{"issue":"2","key":"S0129054122440014BIB021","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","volume":"168","author":"Rogozhin Yu.","year":"1996","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"S0129054122440014BIB022","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0304-3975(94)00278-9","volume":"142","author":"S\u00e9nizergues G.","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"S0129054122440014BIB023","first-page":"133","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics","author":"Thomas W.","year":"1990"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122440014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T07:53:12Z","timestamp":1679298792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122440014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":22,"journal-issue":{"issue":"02n03","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S0129054122440014"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122440014","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]}}}