Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/36416
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChatterjee, Krishnendu-
dc.contributor.authorPiterman, Nir-
dc.date.accessioned2016-01-27T11:09:15Z-
dc.date.available2017-07-06T01:45:06Z-
dc.date.issued2017-06-19-
dc.identifier.citationJournal of Symbolic Logic, 2017, 82(2) pp. 420-452en
dc.identifier.issn0022-4812-
dc.identifier.urihttps://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/obligation-blackwell-games-and-pautomata/4203C70159A8686805FB0321067CDAFAen
dc.identifier.urihttp://hdl.handle.net/2381/36416-
dc.description.abstractWe 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.en
dc.language.isoenen
dc.rightsCopyright © 2017, Association for Symbolic Logic. Deposited with reference to the publisher’s open access archiving policy.en
dc.titleObligation Blackwell Games and p-Automataen
dc.typeJournal Articleen
dc.identifier.doi10.1017/jsl.2016.71-
dc.identifier.eissn1943-5886-
dc.description.statusPeer-revieweden
dc.description.versionPublisher Versionen
dc.type.subtypeArticle-
pubs.organisational-group/Organisationen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
dc.dateaccepted2015-10-23-
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
obligation_blackwell_games_and_pautomata.pdfPublished (publisher PDF)645.76 kBAdobe PDFView/Open


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