{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:32:13Z","timestamp":1787236333871,"version":"build-2736575974"},"reference-count":25,"publisher":"IEEE","license":[{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,26]]},"DOI":"10.1109\/lics56636.2023.10175798","type":"proceedings-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T13:18:23Z","timestamp":1689340703000},"page":"1-13","source":"Crossref","is-referenced-by-count":1,"title":["The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)"],"prefix":"10.1109","author":[{"given":"Laure","family":"Daviaud","sequence":"first","affiliation":[{"name":"CitAI, City, University of London,UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Purser","sequence":"additional","affiliation":[{"name":"University of Liverpool,UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref13","first-page":"41:1","article-title":"The big-O problem for labelled markov chains and weighted automata","volume":"171","author":"chistikov","year":"0"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24372-1_37"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533336"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(1:40)2022"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"104651","DOI":"10.1016\/j.ic.2020.104651","article-title":"What’s decidable about weighted automata?","volume":"282","author":"almagor","year":"2022","journal-title":"Inf Comput"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196794000063"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_12"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74240-1_20"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90269-8"},{"key":"ref18","first-page":"574","article-title":"Approximate comparison of distance automata","volume":"20","author":"colcombet","year":"0"},{"key":"ref24","first-page":"589","article-title":"Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata","volume":"3","author":"kirsten","year":"0"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85238-4_36"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(2:12)2015"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573140"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90047-L"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1994283-402771"},{"key":"ref8","author":"paz","year":"2014","journal-title":"Introduction to Probabilistic Automata"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(1:8)2013"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.01.006"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1006\/csla.2001.0184"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.12"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_18"}],"event":{"name":"2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","location":"Boston, MA, USA","start":{"date-parts":[[2023,6,26]]},"end":{"date-parts":[[2023,6,29]]}},"container-title":["2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/10175635\/10175671\/10175798.pdf?arnumber=10175798","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T13:58:39Z","timestamp":1690898319000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10175798\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,26]]},"references-count":25,"URL":"https:\/\/doi.org\/10.1109\/lics56636.2023.10175798","relation":{},"subject":[],"published":{"date-parts":[[2023,6,26]]}}}