The Complexity of Rational Synthesis
Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, Jean-François Raskin · arXiv (Cornell University) · 2016
We study the computational complexity of the cooperative and non-cooperative rational synthesis problems, as introduced by Kupferman, Vardi and co-authors. We provide tight results for most of the classical omega-regular objectives, and show how to solve those problems optimally.