{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:19Z","timestamp":1753894399939,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A nondeterministic automaton is history-deterministic if its nondeterminism\ncan be resolved by only considering the prefix of the word read so far. Due to\ntheir good compositional properties, history-deterministic automata are useful\nin solving games and synthesis problems. Deciding whether a given\nnondeterministic automaton is history-deterministic (the HDness problem) is\ngenerally a difficult task, which can involve an exponential procedure, or even\nbe undecidable, as is the case for example with pushdown automata. Token games\nprovide a PTime solution to the HDness problem of B\\\"uchi and coB\\\"uchi\nautomata, and it is conjectured that 2-token games characterise HDness for all\n$\\omega$-regular automata.\n  We extend token games to the quantitative setting and analyse their potential\nto help deciding HDness of quantitative automata. In particular, we show that\n1-token games characterise HDness for all quantitative (and Boolean) automata\non finite words, as well as discounted-sum (DSum), Inf and Reachability\nautomata on infinite words, and that 2-token games characterise HDness of\nLimInf and LimSup automata, as well as Sup automata on infinite words. Using\nthese characterisations, we provide solutions to the HDness problem of Safety,\nReachability, Inf and Sup automata on finite and infinite words in PTime, of\nDSum automata on finite and infinite words in NP$\\cap$co-NP, of LimSup automata\nin quasipolynomial time, and of LimInf automata in exponential time, where the\nlatter two are only polynomial for automata with a logarithmic number of\nweights.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:8)2023","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T10:45:08Z","timestamp":1699008308000},"source":"Crossref","is-referenced-by-count":1,"title":["Token Games and History-Deterministic Quantitative-Automata"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Udi","family":"Boker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karoliina","family":"Lehtinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,11,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/lmcs.episciences.org\/12506\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/lmcs.episciences.org\/12506\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T10:45:10Z","timestamp":1699008310000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/9922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:8)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2110.14308v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2110.14308v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2110.14308","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2110.14308","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,11,3]]},"article-number":"9922"}}