Church Synthesis Problem for Noisy Input
Yaron Welner (TAU)

Abstract:

We study two variants of infinite games with imperfect information.
In the first variant, in each round player-1 may decide to hide his
move from player-2. This captures situations where the input signal
is subject to fluctuations (noises), and every error in the input
signal can be detected by the controller. In the second variant, all
of player-1 moves are visible to player-2; however, after the game
ends, player-1 may change some of his moves. This captures
situations where the input signal is subject to fluctuations;
however, the controller cannot detect errors in the input signal.

We consider several cases, according to the amount of errors allowed
in the input signal: a fixed number of errors, finitely many errors
and the case where the rate of errors is bounded by a threshold. For
each of these cases we consider games with regular and mean payoff
winning conditions. We investigate the decidability of these games.

There is a natural reduction for some of these games to (perfect
information) multidimensional mean payoff games recently
considered by Chatarjee et al. However, the decidability of the winner of
multidimensional mean payoff games was stated as an open question.
We prove its decidability and provide tight complexity bounds.