Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/36416
Title: Obligation Blackwell Games and p-Automata
Authors: Piterman, Nir
Chatterjee, Krishnendu
First Published: 2016
Citation: Journal of Symbolic Logic (Accepted, In Press)
Abstract: 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.
DOI Link: TBA
ISSN: 0022-4812
eISSN: 1943-5886
Links: http://www.aslonline.org/journals-journal.html
http://hdl.handle.net/2381/36416
Embargo on file until: 1-Jan-10000
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2016, Association for Symbolic Logic. All rights reserved.
Description: The file associated with this record is under a permanent embargo while publication is In Press in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
ChatterjeePitermanJSL.pdfPost-review (final submitted)477.02 kBUnknownView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.