Articles, chapters, papers, reports Department of Computer Science and Engineering

Permanent URI for this collectionhttps://gupea-staging.ub.gu.se/handle/2077/74181

Browse

Browsing Articles, chapters, papers, reports Department of Computer Science and Engineering by Subject "parity games"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Fair Omega-regular Games
    (27th International Conference on Foundations of Software Science and Computation Structures, 2024) Hausmann, Daniel; Piterman, Nir; Saglam, Irmak; Schmuck, Anne-Kathrin
    We consider two-player games over finite graphs in which both players are restricted by fairness constraints on their moves. Given a two player game graph G=(V,E) and a set of fair moves E_f a subset of E a player is said to play fair in G if they choose an edge e in E_f infinitely often whenever the source vertex of e is visited infinitely often. Otherwise, they play unfair. We equip such games with two omega-regular winning conditions alpha and beta deciding the winner of mutually fair and mutually unfair plays, respectively. Whenever one player plays fair and the other plays unfair, the fairly playing player wins the game. The resulting games are called fair alpha/beta games. We formalize fair alpha/beta games and show that they are determined. For fair parity/parity games, i.e., fair alpha/beta games where alpha and beta are given each by a parity condition over G, we provide a polynomial reduction to (normal) parity games via a gadget construction inspired by the reduction of stochastic parity games to parity games. We further give a direct symbolic fixpoint algorithm to solve fair parity/parity games. On a conceptual level, we illustrate the translation between the gadget-based reduction and the direct symbolic algorithm which uncovers the underlying similarities of solution algorithms for fair and stochastic parity games, as well as for the recently considered class of fair games in which only one player is restricted by fair moves.
  • No Thumbnail Available
    Item
    Faster and Smaller Solutions of Obliging Games
    (35th International Conference on Concurrency Theory (CONCUR 2024), 2024) Hausmann, Daniel; Piterman, Nir
    Obliging games have been introduced in the context of the game perspective on reactive synthesis in order to enforce a degree of cooperation between the to-be-synthesized system and the environment. Previous approaches to the analysis of obliging games have been small-step in the sense that they have been based on a reduction to standard (non-obliging) games in which single moves correspond to single moves in the original (obliging) game. Here, we propose a novel, large-step view on obliging games, reducing them to standard games in which single moves encode long-term behaviors in the original game. This not only allows us to give a meaningful definition of the environment winning in obliging games, but also leads to significantly improved bounds on both strategy sizes and the solution runtime for obliging games.