---
_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. <i>Journal
    of Symbolic Logic</i>. 2017;82(2):420-452. doi:<a href="https://doi.org/10.1017/jsl.2016.71">10.1017/jsl.2016.71</a>
  apa: Chatterjee, K., &#38; Piterman, N. (2017). Obligation blackwell games and p-automata.
    <i>Journal of Symbolic Logic</i>. Cambridge University Press. <a href="https://doi.org/10.1017/jsl.2016.71">https://doi.org/10.1017/jsl.2016.71</a>
  chicago: Chatterjee, Krishnendu, and Nir Piterman. “Obligation Blackwell Games and
    P-Automata.” <i>Journal of Symbolic Logic</i>. Cambridge University Press, 2017.
    <a href="https://doi.org/10.1017/jsl.2016.71">https://doi.org/10.1017/jsl.2016.71</a>.
  ieee: K. Chatterjee and N. Piterman, “Obligation blackwell games and p-automata,”
    <i>Journal of Symbolic Logic</i>, 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.”
    <i>Journal of Symbolic Logic</i>, vol. 82, no. 2, Cambridge University Press,
    2017, pp. 420–52, doi:<a href="https://doi.org/10.1017/jsl.2016.71">10.1017/jsl.2016.71</a>.
  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'
...