No Cover Image

Conference Paper/Proceeding/Abstract 182 views 7 downloads

Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions / Stephane Le Roux; Arno Pauly; 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

  • LIPIcs-FSTTCS-2018-38.pdf

    PDF | Version of Record

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

    Download (531.31KB)

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: College of Science
Start Page: 38:1
End Page: 38:20