2010 | OriginalPaper | Buchkapitel
Asynchronous Omega-Regular Games with Partial Information
verfasst von : Bernd Puchala
Erschienen in: Mathematical Foundations of Computer Science 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We address the strategy problem for
ω
-regular two-player games with partial information, played on finite game graphs. We consider two different kinds of observability on a general model, a standard synchronous and an asynchronous one. In the asynchronous setting, moves which have no visible effect for a player are hidden completely from that player. We generalize the usual powerset construction for eliminating partial information to arbitrary, not necessarily observation based, winning conditions, both in the synchronous and in the asynchronous case, and we show that this generalized construction effectively preserves
ω
-regular winning conditions. From this we infer decidability of the strategy problem for arbitrary
ω
-regular winning conditions, in both cases. We also show that our
ω
-regular framework is sufficient for reasoning about synchronous and asynchronous knowledge by proving that any formula of the epistemic temporal specification formalism ETL can be effectively translated into an S1S-formula defining the same specification.