On the high undecidability of distributed synthesis problemsReport as inadecuate

On the high undecidability of distributed synthesis problems - Download this document for free, or read online. Document in PDF available to download.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : The distributed synthesis problem 11 is known to be undecidable. Our purpose here is to study further this undecidability. For this, we consider distributed games 8, an infinite variant of Peterson and Reif multiplayer games with partial information 10, in which Pnueli and Rosner?s distributed synthesis problem can be encoded and, when decidable 11,6,7, uniformly solved 8. We first prove that even the simple problem of solving 2-process distributed game with reachability conditions is undecidable $\Sigma^0 1$ -complete. This decision problem, equivalent to two process distributed synthesis with fairly restricted FO-specification was left open 8. We prove then that the safety case is $\Pi^0 1$ -complete. More generally, we establish a correspondence between 2-process distributed game with Mostowski?s weak parity conditions 9 and levels of the arithmetical hierarchy. finally, distributed games with general ?-regular infinitary conditions are shown to be highly undecidable $\Sigma^1 1$ -complete

Author: David Janin -

Source: https://hal.archives-ouvertes.fr/


Related documents