We consider games over a finite arena with set of vertices V. A history is a word over V, and the information of a player is an equivalence relation over histories.

Given such an equivalence relation over histories, we want to synthesize an observation function V*->O*, which maps equivalent histories to identical observations and non-equivalent histories to different observations.

Given a sequential observation function, we are able to define a new arena V' with an equivalence relation ~ over V' such that two histories are equivalent iff they are letter-to-letter equivalent under ~.

We show that the observation synthesis problem is decidable when the target function is letter-to-letter, and in that case we can effectively synthesize an observation function. We also show that the problem is undecidable in a slightly more general case.

Joint work with Paulin Fournier and Bruno Guillon