@InProceedings{   CachatDuparcThomas:CSL:2002,
  Author        = "Cachat, Thierry and Duparc, Jacques and Thomas, Wolfgang",
  Abstract      = "We study infinite two-player games over pushdown graphs with a winning condition that refers explicitly to the infinity of the game graph: A play is won by player 0 if some vertex is visited infinity often during the play. We show that the set of winning plays is a proper 3 -set in the Borel hierarchy, thus transcending the Boolean closure of 2 -sets which arises with the standard automata theoretic winning conditions (such as the Muller, Rabin, or parity condition). We also show that this 3 -game over pushdown graphs can be solved effectively (by a computation of the winning region of player 0 and his memoryless winning strategy). This seems to be a first example of an effectively solvable game beyondt he second level of the Borel hierarchy.",
  Address       = "Berlin, Heidelberg",
  BookTitle     = "Proc. of CSL'02",
  date-added    = "2020-08-19 11:59:53 +0200",
  date-modified = "2020-08-19 12:00:14 +0200",
  ISBN          = "3540442405",
  numpages      = "15",
  Pages         = "322---336",
  Publisher     = "Springer-Verlag",
  Title         = "Solving Pushdown Games with a Sigma3 Winning Condition",
  Year          = "2002",
  File          = "Solving Pushdown Games with a Sigma3 Winning Condition - cdt02bCSL - a - a - a.pdf"
}

@InProceedings{ CachatDuparcThomas:CSL:2002, Author = "Cachat, Thierry and Duparc, Jacques and Thomas, Wolfgang", Abstract = "We study infinite two-player games over pushdown graphs with a winning condition that refers explicitly to the infinity of the game graph: A play is won by player 0 if some vertex is visited infinity often during the play. We show that the set of winning plays is a proper 3 -set in the Borel hierarchy, thus transcending the Boolean closure of 2 -sets which arises with the standard automata theoretic winning conditions (such as the Muller, Rabin, or parity condition). We also show that this 3 -game over pushdown graphs can be solved effectively (by a computation of the winning region of player 0 and his memoryless winning strategy). This seems to be a first example of an effectively solvable game beyondt he second level of the Borel hierarchy.", Address = "Berlin, Heidelberg", BookTitle = "Proc. of CSL'02", date-added = "2020-08-19 11:59:53 +0200", date-modified = "2020-08-19 12:00:14 +0200", ISBN = "3540442405", numpages = "15", Pages = "322---336", Publisher = "Springer-Verlag", Title = "Solving Pushdown Games with a Sigma3 Winning Condition", Year = "2002", File = "Solving Pushdown Games with a Sigma3 Winning Condition - cdt02bCSL - a - a - a.pdf" }