---
_id: '4547'
abstract:
- lang: eng
text: We study observation-based strategies for two-player turn-based games on graphs
with omega-regular objectives. An observation-based strategy relies on imperfect
information about the history of a play, namely, on the past sequence of observations.
Such games occur in the synthesis of a controller that does not see the private
state of the plant. Our main results are twofold. First, we give a fixed-point
algorithm for computing the set of states from which a player can win with a deterministic
observation-based strategy for any omega-regular objective. The fixed point is
computed in the lattice of antichains of state sets. This algorithm has the advantages
of being directed by the objective and of avoiding an explicit subset construction
on the game graph. Second, we give an algorithm for computing the set of states
from which a player can win with probability 1 with a randomized observation-based
strategy for a Buechi objective. This set is of interest because in the absence
of perfect information, randomized strategies are more powerful than deterministic
ones. We show that our algorithms are optimal by proving matching lower bounds.
acknowledgement: This research was supported in part by the NSF grants CCR-0225610
and CCR-0234690 by the SNSF under the Indo-Swiss Joint Research Programme and by
the FRFC project “Centre Fédéré en Vérification” funded by the FNRS under grant
2.4530.02.
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Thomas Henzinger
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jean
full_name: Raskin, Jean-François
last_name: Raskin
citation:
ama: Chatterjee K, Doyen L, Henzinger TA, Raskin J. Algorithms for omega-regular
games with imperfect information. Logical Methods in Computer Science.
2007;3(184):1-23. doi:10.2168/LMCS-3(3:4)2007
apa: Chatterjee, K., Doyen, L., Henzinger, T. A., & Raskin, J. (2007). Algorithms
for omega-regular games with imperfect information. Logical Methods in Computer
Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-3(3:4)2007
chicago: Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin.
“Algorithms for Omega-Regular Games with Imperfect Information.” Logical Methods
in Computer Science. International Federation of Computational Logic, 2007.
https://doi.org/10.2168/LMCS-3(3:4)2007.
ieee: K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Algorithms for omega-regular
games with imperfect information,” Logical Methods in Computer Science,
vol. 3, no. 184. International Federation of Computational Logic, pp. 1–23, 2007.
ista: Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2007. Algorithms for omega-regular
games with imperfect information. Logical Methods in Computer Science. 3(184),
1–23.
mla: Chatterjee, Krishnendu, et al. “Algorithms for Omega-Regular Games with Imperfect
Information.” Logical Methods in Computer Science, vol. 3, no. 184, International
Federation of Computational Logic, 2007, pp. 1–23, doi:10.2168/LMCS-3(3:4)2007.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, J. Raskin, Logical Methods in Computer
Science 3 (2007) 1–23.
date_created: 2018-12-11T12:09:25Z
date_published: 2007-07-27T00:00:00Z
date_updated: 2021-01-12T07:59:36Z
day: '27'
doi: 10.2168/LMCS-3(3:4)2007
extern: 1
intvolume: ' 3'
issue: 184
month: '07'
page: 1 - 23
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '167'
quality_controlled: 0
status: public
title: Algorithms for omega-regular games with imperfect information
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
volume: 3
year: '2007'
...