{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:50Z","timestamp":1750220750789,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T00:00:00Z","timestamp":1588118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2020,4,29]]},"abstract":"<jats:p>We survey some results about the sequentiality problem for max-plus automata and its generalisation, the register complexity problem for cost register automata. We compare classes of functions computed by maxplus automata and by cost register automata with respect to the notion of ambiguity. The two models are introduced gently, so the novice reader is welcome!<\/jats:p>","DOI":"10.1145\/3397619.3397621","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T18:32:45Z","timestamp":1588617165000},"page":"4-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Register complexity and determinisation of max-plus automata"],"prefix":"10.1145","volume":"7","author":[{"given":"Laure","family":"Daviaud","sequence":"first","affiliation":[{"name":"CitAI, City University of London"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,4,29]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/978-3-540-85780-8_8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/LICS.2013.65"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/978-3-642-39212-2_7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/978-3-642-40313-2_10"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1007\/978-3-642-37064-9_11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/0304-3975(82)90019-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1016\/S0019-9958(77)90050-X"},{"unstructured":"Agnishom Chattopadhyay Filip Mazowiecki Anca Muscholl and Cristian Riveros. 2020. Pumping lemmas for weighted automata. CoRR abs\/2001.06272 (2020). https:\/\/arxiv.org\/abs\/2001.06272  Agnishom Chattopadhyay Filip Mazowiecki Anca Muscholl and Cristian Riveros. 2020. Pumping lemmas for weighted automata. CoRR abs\/2001.06272 (2020). https:\/\/arxiv.org\/abs\/2001.06272","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/978-3-662-44522-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.4230\/LIPIcs.MFCS.2017.19"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/2933575.2934549"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/9.754807"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/0890-5401(88)90033-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1051\/ita:2008017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.4230\/LIPIcs.STACS.2009.1850"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1016\/j.tcs.2004.02.049"},{"volume-title":"Proceedings of the 3rd International Conference Developments in Language Theory, DLT 1997","year":"1997","author":"Kuich Werner","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.4230\/LIPIcs.STACS.2018.50"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.5555\/972695.972698"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1006\/csla.2001.0184"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.4230\/LIPIcs.MFCS.2017.53"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.4230\/LIPIcs.STACS.2019.55"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/S0019-9958(61)80020-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1016\/0304-3975(94)90271-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1109\/SFCS.1978.21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/BFb0017135"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.25596\/jalc-2007-545"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1016\/0304-3975(91)90381-B"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397619.3397621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397619.3397621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:53Z","timestamp":1750199933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397619.3397621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,29]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,29]]}},"alternative-id":["10.1145\/3397619.3397621"],"URL":"https:\/\/doi.org\/10.1145\/3397619.3397621","relation":{},"ISSN":["2372-3491"],"issn-type":[{"type":"electronic","value":"2372-3491"}],"subject":[],"published":{"date-parts":[[2020,4,29]]},"assertion":[{"value":"2020-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}