{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:19Z","timestamp":1760202679823,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,9,27]],"date-time":"2012-09-27T00:00:00Z","timestamp":1348704000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study variants of regular infinite games where the strict alternation of\nmoves between the two players is subject to modifications. The second player\nmay postpone a move for a finite number of steps, or, in other words, exploit\nin his strategy some lookahead on the moves of the opponent. This captures\nsituations in distributed systems, e.g. when buffers are present in\ncommunication or when signal transmission between components is deferred. We\ndistinguish strategies with different degrees of lookahead, among them being\nthe continuous and the bounded lookahead strategies. In the first case the\nlookahead is of finite possibly unbounded size, whereas in the second case it\nis of bounded size. We show that for regular infinite games the solvability by\ncontinuous strategies is decidable, and that a continuous strategy can always\nbe reduced to one of bounded lookahead. Moreover, this lookahead is at most\ndoubly exponential in the size of a given parity automaton recognizing the\nwinning condition. We also show that the result fails for non-regular\ngamesxwhere the winning condition is given by a context-free omega-language.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:24)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":13,"title":["Degrees of Lookahead in Regular Infinite Games"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"given":"Michael","family":"Holtmann","sequence":"first","affiliation":[]},{"given":"Lukasz","family":"Kaiser","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Thomas","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,9,27]]},"reference":[{"key":"556:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/922\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/922\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:59:07Z","timestamp":1681243147000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,27]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:24)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1209.0800","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1209.0800","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,9,27]]},"article-number":"922"}}