Playing Games in the Baire Space

Benedikt Brütsch
(RWTH Aachen University)
Wolfgang Thomas
(RWTH Aachen University)

We solve a generalized version of Church's Synthesis Problem where a play is given by a sequence of natural numbers rather than a sequence of bits; so a play is an element of the Baire space rather than of the Cantor space. Two players Input and Output choose natural numbers in alternation to generate a play. We present a natural model of automata ("N-memory automata") equipped with the parity acceptance condition, and we introduce also the corresponding model of "N-memory transducers". We show that solvability of games specified by N-memory automata (i.e., existence of a winning strategy for player Output) is decidable, and that in this case an N-memory transducer can be constructed that implements a winning strategy for player Output.

In Thomas Brihaye, Benoît Delahaye, Loïg Jezequel, Nicolas Markey and Jiří Srba: Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16), Eindhoven, The Netherlands, April 2-3, 2016, Electronic Proceedings in Theoretical Computer Science 220, pp. 13–25.
Published: 31st July 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.220.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org