On the high undecidability of distributed synthesis problemsReportar como inadecuado

On the high undecidability of distributed synthesis problems - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: David Janin -

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


Documentos relacionados