{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T11:14:07Z","timestamp":1690974847877},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","funder":[{"name":"the European Union's Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie","award":["837327"],"award-info":[{"award-number":["837327"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-10-IDEX-03-02"],"award-info":[{"award-number":["ANR-10-IDEX-03-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over [Formula: see text] with updates using [Formula: see text] and increments. We show that this model can simulate, in some sense, the runs of counter machines with zero-tests. We deduce that a number of problems pertaining to that model are undecidable, namely equivalence, upperboundedness, and semilinearity. In particular, the undecidability of equivalence disproves a conjecture of Alur et al. from 2012. To emphasize how weak these machines are, we also show that they can be expressed as a restricted form of linearly-ambiguous weighted automata. <\/jats:p>","DOI":"10.1142\/s0129054120410026","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:57:28Z","timestamp":1605257848000},"page":"689-709","source":"Crossref","is-referenced-by-count":1,"title":["Weak Cost Register Automata are Still Powerful"],"prefix":"10.1142","volume":"31","author":[{"given":"Shaull","family":"Almagor","sequence":"first","affiliation":[{"name":"Computer Science Department, Technion, Haifa 3200003, Israel"}]},{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"additional","affiliation":[{"name":"College of Computing and Digital Media, DePaul University, 243 S Wabash Ave, Chicago, IL 60604, USA"}]},{"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[{"name":"Laboratoire Bordelais de Recherche en Informatique (UMR 5800), 351 cours de la Lib\u00e9ration, 33405 Talence CEDEX, France"}]},{"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"Universiteit Antwerpen, Campus Middelheim, Middelheimlaan 1, 2020 Antwerpen, Belgi\u00eb"}]}],"member":"219","published-online":{"date-parts":[[2020,10,22]]},"reference":[{"key":"S0129054120410026BIB001","first-page":"482","volume-title":"ATVA 2011","author":"Almagor S.","year":"2011"},{"key":"S0129054120410026BIB002","first-page":"1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010","author":"Alur R.","year":"2010"},{"key":"S0129054120410026BIB003","first-page":"13","volume-title":"LICS 2013","author":"Alur R.","year":"2013"},{"issue":"2","key":"S0129054120410026BIB004","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0304-3975(94)90010-8","volume":"126","author":"Alur R.","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120410026BIB005","first-page":"1","volume-title":"32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017","author":"Benedikt M.","year":"2017"},{"key":"S0129054120410026BIB006","first-page":"14:1","volume-title":"29th International Conference on Concurrency Theory, CONCUR 2018","author":"Blondin M.","year":"2018"},{"issue":"7","key":"S0129054120410026BIB007","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1142\/S0129054113400339","volume":"24","author":"Cadilhac M.","year":"2013","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"S0129054120410026BIB008","first-page":"153","volume":"40","author":"Gaubert S.","year":"2004","journal-title":"Kybernetika"},{"issue":"2","key":"S0129054120410026BIB009","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(82)90051-4","volume":"24","author":"Hashiguchi K.","year":"1982","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"S0129054120410026BIB010","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"Kaminski M.","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120410026BIB011","first-page":"589","volume-title":"Proc. 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009","author":"Kirsten D.","year":"2009"},{"key":"S0129054120410026BIB012","first-page":"53:1","volume-title":"STACS 2016","author":"Mazowiecki F.","year":"2016"},{"issue":"3","key":"S0129054120410026BIB013","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"Minsky M. L.","year":"1961","journal-title":"Annals of Mathematics"},{"key":"S0129054120410026BIB015","first-page":"92","volume-title":"Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticiens des Pays Slaves","author":"Presburger M.","year":"1927"},{"key":"S0129054120410026BIB016","first-page":"24","volume-title":"Computer Science \u2014 Theory and Applications Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings","author":"S\u00e9nizergues G.","year":"2007"},{"issue":"2","key":"S0129054120410026BIB017","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"Weber A.","year":"1991","journal-title":"Theoretical Computer Science"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120410026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:59:13Z","timestamp":1605257953000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120410026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":16,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0129054120410026"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120410026","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}