Games with winning conditions of high Borel complexity

We first consider infinite two-player games on pushdown graphs. In previous work, Cachat et al. [Solving pushdown games with a Σ 3 -winning condition, in: Proc. 11th Annu. Conf. of the European Association for Computer Science Logic, CSL 2002, Lecture Notes in Computer Science, Vol. 2471, Springer,...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2006, Vol.350 (2), p.345-372
Main Author: Serre, Olivier
Format: Article
Language:English
Subjects:
Applied sciences
Automata. Abstract machines. Turing machines
Borel complexity
Computation and Language
Computer Science
Computer science
control theory
systems
Exact sciences and technology
Logic and foundations
Mathematical logic, foundations, set theory
Mathematics
Pushdown automata
Recursion theory
Sciences and techniques of general use
Theoretical computing
Two-player games
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We first consider infinite two-player games on pushdown graphs. In previous work, Cachat et al. [Solving pushdown games with a Σ 3 -winning condition, in: Proc. 11th Annu. Conf. of the European Association for Computer Science Logic, CSL 2002, Lecture Notes in Computer Science, Vol. 2471, Springer, Berlin, 2002, pp. 322–336] 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 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 conditions is shown to be non-elementary.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2005.10.024