{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T22:55:45Z","timestamp":1752360945181,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030992521"},{"type":"electronic","value":"9783030992538"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"vor","delay-in-days":87,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional properties, history-deterministic automata are useful in solving games and synthesis problems. Deciding whether a given nondeterministic automaton is history-deterministic (the problem) is generally a difficult task, which might involve an exponential procedure, or even be undecidable, for example for pushdown automata.<jats:italic>Token games<\/jats:italic>provide a<jats:sc>PTime<\/jats:sc>solution to the problem of B\u00fcchi and coB\u00fcchi automata, and it is conjectured that 2-token games characterise for all<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c9<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-regular automata. We extend token games to the quantitative setting and analyze their potential to help deciding for quantitative automata. In particular, we show that 1-token games characterise for all quantitative (and Boolean) automata on finite words, as well as discounted-sum (<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {DSum}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>DSum<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) automata on infinite words, and that 2-token games characterise of<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {LimInf}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>LimInf<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {LimSup}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>LimSup<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>automata. Using these characterisations, we provide solutions to the problem of<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {Inf}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Inf<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {Sup}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Sup<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>automata on finite words in<jats:sc>PTime<\/jats:sc>, for<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {DSum}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>DSum<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>automata on finite and infinite words in<jats:sc>NP<\/jats:sc><jats:inline-formula><jats:alternatives><jats:tex-math>$$\\cap $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>\u2229<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula><jats:sc>co-NP<\/jats:sc>, for<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {LimSup}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>LimSup<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>automata in quasipolynomial time, and for<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {LimInf}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>LimInf<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>automata in exponential time, where the latter two are only polynomial for automata with a logarithmic number of weights.<\/jats:p>","DOI":"10.1007\/978-3-030-99253-8_7","type":"book-chapter","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:02:48Z","timestamp":1648497768000},"page":"120-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Token Games and History-Deterministic Quantitative Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4322-8892","authenticated-orcid":false,"given":"Udi","family":"Boker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1171-8790","authenticated-orcid":false,"given":"Karoliina","family":"Lehtinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Benjamin Aminof, Orna Kupferman, and Robby Lampert. Reasoning about online algorithms with weighted automata. ACM Trans. Algorithms, 6(2):28:1\u201328:36, 2010.","key":"7_CR1","DOI":"10.1145\/1721837.1721844"},{"unstructured":"Daniel Andersson. An improved algorithm for discounted payoff games. In Proc. of ESSLLI Student Session, pages 91\u201398, 2006.","key":"7_CR2"},{"unstructured":"Marc Bagnol and Denis Kuperberg. B\u00fcchi good-for-games automata are efficiently recognizable. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), page\u00a016, 2018.","key":"7_CR3"},{"doi-asserted-by":"crossref","unstructured":"Udi Boker. Why these automata types? In Proceedings of LPAR, pages 143\u2013163, 2018.","key":"7_CR4","DOI":"10.29007\/c3bj"},{"doi-asserted-by":"crossref","unstructured":"Udi Boker. Quantitative vs. weighted automata. In Proc. of Reachbility Problems, pages 1\u201316, 2021.","key":"7_CR5","DOI":"10.1007\/978-3-030-89716-1_1"},{"unstructured":"Udi Boker, Denis Kuperberg, Karoliina Lehtinen, and Micha\u0142 Skrzypczak. On succinctness and recognisability of alternating good-for-games automata. arXiv preprint\u00a0 arXiv:2002.07278, 2020.","key":"7_CR6"},{"unstructured":"Udi Boker and Karoliina Lehtinen. Good for games automata: From nondeterminism to alternation. In Proceedings of CONCUR, volume 140 of LIPIcs, pages 19:1\u201319:16, 2019.","key":"7_CR7"},{"unstructured":"Udi Boker and Karoliina Lehtinen. History determinism vs. good for gameness in quantitative automata. In Proc. of FSTTCS, pages 35:1\u201335:20, 2021.","key":"7_CR8"},{"doi-asserted-by":"crossref","unstructured":"Cristian\u00a0S Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of STOC, pages 252\u2013263, 2017.","key":"7_CR9","DOI":"10.1145\/3055399.3055409"},{"doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee, Laurent Doyen, and Thomas\u00a0A. Henzinger. Quantitative languages. ACM Trans. Comput. Log., 11(4):23:1\u201323:38, 2010.","key":"7_CR10","DOI":"10.1145\/1805950.1805953"},{"doi-asserted-by":"crossref","unstructured":"Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In Proceedings of ICALP, pages 139\u2013150, 2009.","key":"7_CR11","DOI":"10.1007\/978-3-642-02930-1_12"},{"doi-asserted-by":"crossref","unstructured":"Thomas Colcombet and Nathana\u00ebl Fijalkow. Universal graphs and good for games automata: New tools for infinite duration games. In Proc. of FOSSACS, volume 11425 of Lecture Notes in Computer Science, pages 1\u201326. Springer, 2019.","key":"7_CR12","DOI":"10.1007\/978-3-030-17127-8_1"},{"doi-asserted-by":"crossref","unstructured":"Emmanuel Filiot, Isma\u00ebl Jecker, Nathan Lhote, Guillermo\u00a0A. P\u00e9rez, and Jean-Fran\u00e7ois Raskin. On delay and regret determinization of max-plus automata. In LICS, pages 1\u201312, 2017.","key":"7_CR13","DOI":"10.1109\/LICS.2017.8005096"},{"unstructured":"Emmanuel Filiot, Christof L\u00f6ding, and Sarah Winter. Synthesis from weighted specifications with partial domains over finite words. In Nitin Saxena and Sunil Simon, editors, FSTTCS, volume 182 of LIPIcs, pages 46:1\u201346:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020.","key":"7_CR14"},{"unstructured":"Shibashis Guha, Isma\u00ebl Jecker, Karoliina Lehtinen, and Martin Zimmermann. A bit of nondeterminism makes pushdown automata expressive and succinct. In Proc. of MFCS, pages 53:1\u201353:20, 2021.","key":"7_CR15"},{"doi-asserted-by":"crossref","unstructured":"Thomas Henzinger and Nir Piterman. Solving games without determinization. In Proceedings of CSL, pages 395\u2013410, 2006.","key":"7_CR16","DOI":"10.1007\/11874683_26"},{"doi-asserted-by":"crossref","unstructured":"Paul Hunter, Guillermo\u00a0A. P\u00e9rez, and Jean-Fran\u00e7ois Raskin. Minimizing regret in discounted-sum games. In Jean-Marc Talbot and Laurent Regnier, editors, CSL, volume\u00a062 of LIPIcs, pages 30:1\u201330:17, 2016.","key":"7_CR17","DOI":"10.1021\/cen-09443-cover6"},{"doi-asserted-by":"crossref","unstructured":"Paul Hunter, Guillermo\u00a0A. P\u00e9rez, and Jean-Fran\u00e7ois Raskin. Reactive synthesis without regret. Acta Informatica, 54(1):3\u201339, 2017.","key":"7_CR18","DOI":"10.1007\/s00236-016-0268-z"},{"doi-asserted-by":"crossref","unstructured":"Denis Kuperberg and Micha\u0142 Skrzypczak. On determinisation of good-for-games automata. In Proceedings of ICALP, pages 299\u2013310, 2015.","key":"7_CR19","DOI":"10.1007\/978-3-662-47666-6_24"},{"doi-asserted-by":"crossref","unstructured":"Karoliina Lehtinen and Martin Zimmermann. Good-for-games $$\\omega $$-pushdown automata. In LICS20, pages 689\u2013702, 2020.","key":"7_CR20","DOI":"10.1145\/3373718.3394737"},{"unstructured":"Anirban Majumdar and Denis Kuperberg. Computing the width of non-deterministic automata. Logical Methods in Computer Science, 15, 2019.","key":"7_CR21"},{"doi-asserted-by":"crossref","unstructured":"L.\u00a0S. Shapley. Stochastic games. In Proc. of Nat. Acad. Sci., volume\u00a039, pages 1095\u20131100, 1953.","key":"7_CR22","DOI":"10.1073\/pnas.39.10.1095"},{"doi-asserted-by":"crossref","unstructured":"Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Electron. Colloquium Comput. Complex., 2(40), 1995.","key":"7_CR23","DOI":"10.1007\/BFb0030814"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99253-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T04:21:23Z","timestamp":1726892483000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99253-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030992521","9783030992538"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99253-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"77","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}