Conference Paper/Proceeding/Abstract 796 views 81 downloads
Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Volume: 122, Pages: 38:1 - 38:20
Swansea University Author:
Arno Pauly
-
PDF | Version of Record
Released under the terms of a Creative Commons License (CC-BY).
Download (531.31KB)
DOI (Published version): 10.4230/LIPIcs.FSTTCS.2018.38
Abstract
We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objecti...
Published in: | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) |
---|---|
ISBN: | 978-3-95977-093-4 |
ISSN: | 1868-8969 |
Published: |
FSTTCS
2018
|
Online Access: |
Check full text
|
URI: | https://cronfa.swan.ac.uk/Record/cronfa47957 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Abstract: |
We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objective setting. We show that our framework encompasses important classes of games from the literature, and permits to go further, using a unified approach. While such an approach cannot match ad-hoc proofs with regard to tightness of memory bounds, it has two advantages: first, it gives a widely-applicable criterion for FM determinacy; second, it helps to understand the cornerstones of FM determinacy, which are often hidden but common in proofs for specific (combinations of) winning conditions. |
---|---|
College: |
Faculty of Science and Engineering |
Start Page: |
38:1 |
End Page: |
38:20 |