{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:21Z","timestamp":1753894401272,"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>This paper presents a case study for the application of semiring semantics\nfor fixed-point formulae to the analysis of strategies in B\\\"uchi games.\nSemiring semantics generalizes the classical Boolean semantics by permitting\nmultiple truth values from certain semirings. Evaluating the fixed-point\nformula that defines the winning region in a given game in an appropriate\nsemiring of polynomials provides not only the Boolean information on who wins,\nbut also tells us how they win and which strategies they might use. This is\nwell-understood for reachability games, where the winning region is definable\nas a least fixed point. The case of B\\\"uchi games is of special interest, not\nonly due to their practical importance, but also because it is the simplest\ncase where the fixed-point definition involves a genuine alternation of a\ngreatest and a least fixed point. We show that, in a precise sense, semiring\nsemantics provide information about all absorption-dominant strategies --\nstrategies that win with minimal effort, and we discuss how these relate to\npositional and the more general persistent strategies. This information enables\napplications such as game synthesis or determining minimal modifications to the\ngame needed to change its outcome. Lastly, we discuss limitations of our\napproach and present questions that cannot be immediately answered by semiring\nsemantics.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:21)2024","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T10:35:12Z","timestamp":1710153312000},"source":"Crossref","is-referenced-by-count":0,"title":["Semiring Provenance for B\\\"uchi Games: Strategy Analysis with Absorptive Polynomials"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niels","family":"L\u00fccking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Naaf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,3,8]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13205\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13205\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T10:35:12Z","timestamp":1710153312000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:21)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2106.12892v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2106.12892v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2106.12892","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2106.12892","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,3,8]]},"article-number":"9049"}}