--- _id: '684' abstract: - lang: eng text: We generalize winning conditions in two-player games by adding a structural acceptance condition called obligations. Obligations are orthogonal to the linear winning conditions that define whether a play is winning. Obligations are a declaration that player 0 can achieve a certain value from a configuration. If the obligation is met, the value of that configuration for player 0 is 1. We define the value in such games and show that obligation games are determined. For Markov chains with Borel objectives and obligations, and finite turn-based stochastic parity games with obligations we give an alternative and simpler characterization of the value function. Based on this simpler definition we show that the decision problem of winning finite turn-based stochastic parity games with obligations is in NP∩co-NP. We also show that obligation games provide a game framework for reasoning about p-automata. © 2017 The Association for Symbolic Logic. article_processing_charge: No author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Nir full_name: Piterman, Nir last_name: Piterman citation: ama: Chatterjee K, Piterman N. Obligation blackwell games and p-automata. Journal of Symbolic Logic. 2017;82(2):420-452. doi:10.1017/jsl.2016.71 apa: Chatterjee, K., & Piterman, N. (2017). Obligation blackwell games and p-automata. Journal of Symbolic Logic. Cambridge University Press. https://doi.org/10.1017/jsl.2016.71 chicago: Chatterjee, Krishnendu, and Nir Piterman. “Obligation Blackwell Games and P-Automata.” Journal of Symbolic Logic. Cambridge University Press, 2017. https://doi.org/10.1017/jsl.2016.71. ieee: K. Chatterjee and N. Piterman, “Obligation blackwell games and p-automata,” Journal of Symbolic Logic, vol. 82, no. 2. Cambridge University Press, pp. 420–452, 2017. ista: Chatterjee K, Piterman N. 2017. Obligation blackwell games and p-automata. Journal of Symbolic Logic. 82(2), 420–452. mla: Chatterjee, Krishnendu, and Nir Piterman. “Obligation Blackwell Games and P-Automata.” Journal of Symbolic Logic, vol. 82, no. 2, Cambridge University Press, 2017, pp. 420–52, doi:10.1017/jsl.2016.71. short: K. Chatterjee, N. Piterman, Journal of Symbolic Logic 82 (2017) 420–452. date_created: 2018-12-11T11:47:54Z date_published: 2017-06-01T00:00:00Z date_updated: 2021-04-16T12:10:53Z day: '01' department: - _id: KrCh doi: 10.1017/jsl.2016.71 intvolume: ' 82' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1206.5174 month: '06' oa: 1 oa_version: Submitted Version page: 420 - 452 publication: Journal of Symbolic Logic publication_identifier: eissn: - 1943-5886 issn: - 0022-4812 publication_status: published publisher: Cambridge University Press publist_id: '7026' quality_controlled: '1' scopus_import: '1' status: public title: Obligation blackwell games and p-automata type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 82 year: '2017' ...