--- _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' ...