Michael Holtmann ; Lukasz Kaiser ; Wolfgang Thomas - Degrees of Lookahead in Regular Infinite Games

lmcs:922 - Logical Methods in Computer Science, September 27, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:24)2012
Degrees of Lookahead in Regular Infinite Games

Authors: Michael Holtmann ; Lukasz Kaiser ; Wolfgang Thomas

    We study variants of regular infinite games where the strict alternation of moves between the two players is subject to modifications. The second player may postpone a move for a finite number of steps, or, in other words, exploit in his strategy some lookahead on the moves of the opponent. This captures situations in distributed systems, e.g. when buffers are present in communication or when signal transmission between components is deferred. We distinguish strategies with different degrees of lookahead, among them being the continuous and the bounded lookahead strategies. In the first case the lookahead is of finite possibly unbounded size, whereas in the second case it is of bounded size. We show that for regular infinite games the solvability by continuous strategies is decidable, and that a continuous strategy can always be reduced to one of bounded lookahead. Moreover, this lookahead is at most doubly exponential in the size of a given parity automaton recognizing the winning condition. We also show that the result fails for non-regular gamesxwhere the winning condition is given by a context-free omega-language.


    Volume: Volume 8, Issue 3
    Published on: September 27, 2012
    Accepted on: June 25, 2015
    Submitted on: December 10, 2010
    Keywords: Computer Science - Formal Languages and Automata Theory,D.2.4

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 1906.04199
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.concur.2020.43
    Source : ScholeXplorer IsCitedBy DOI 10.46298/lmcs-18(2:23)2022
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.1906.04199
    • 10.46298/lmcs-18(2:23)2022
    • 10.48550/arxiv.1906.04199
    • 10.4230/lipics.concur.2020.43
    • 1906.04199
    Synthesis of Computable Regular Functions of Infinite Words
    Dave, Vrunda ; Filiot, Emmanuel ; Krishna, Shankara Narayanan ; Lhote, Nathan ;

    14 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 410 times.
    This article's PDF has been downloaded 599 times.