No Cover Image

Conference Paper/Proceeding/Abstract 858 views 93 downloads

Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Stephane Le Roux, Arno Pauly Orcid Logo, Mickael Randour

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 Orcid Logo

  • LIPIcs-FSTTCS-2018-38.pdf

    PDF | Version of Record

    Released under the terms of a Creative Commons License (CC-BY).

    Download (531.31KB)

Check full text

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...

Full description

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

Similar Items