@inbook{986655e40aa44ccbad9d1500b892d86d,
title = "Games with winning conditions of high Borel complexity",
abstract = "We first consider infinite two-player games on pushdown graphs. In previous work, Cachat, Duparc and Thomas [4] have presented a winning decidable condition that is Σ3-complete in the Borel hierarchy. This was the first example of a decidable winning condition of such Borel complexity. We extend this result by giving a family of decidable winning conditions of arbitrary high finite Borel complexity. From this family, we deduce a family of decidable winning conditions of arbitrary finite Borel complexity for games played on finite graphs. The problem of deciding the winner for these winning conditions is shown to be non-elementary complete.",
keywords = "Borel Complexity, Pushdown Automata, Two-player Games",
author = "Olivier Serre",
year = "2004",
month = jan,
day = "1",
doi = "10.1007/978-3-540-27836-8\_95",
language = "English",
isbn = "3540228497",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "1150--1162",
editor = "Josep D{\'i}az and Juhani Karhum{\"a}ki and Arto Lepist{\"o} and Donald Sannella",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}