No Cover Image

Conference Paper/Proceeding/Abstract 1259 views 149 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
first_indexed 2019-02-04T14:02:56Z
last_indexed 2019-02-04T14:02:56Z
id cronfa47957
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2019-02-04T08:45:32.1208932</datestamp><bib-version>v2</bib-version><id>47957</id><entry>2018-12-13</entry><title>Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2018-12-13</date><deptcode>MACS</deptcode><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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)</journal><volume>122</volume><paginationStart>38:1</paginationStart><paginationEnd>38:20</paginationEnd><publisher>FSTTCS</publisher><isbnElectronic>978-3-95977-093-4</isbnElectronic><issnElectronic>1868-8969</issnElectronic><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-12-31</publishedDate><doi>10.4230/LIPIcs.FSTTCS.2018.38</doi><url>http://drops.dagstuhl.de/opus/volltexte/2018/9937/</url><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2019-02-04T08:45:32.1208932</lastEdited><Created>2018-12-13T11:57:29.6828031</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Stephane</firstname><surname>Le Roux</surname><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>2</order></author><author><firstname>Mickael</firstname><surname>Randour</surname><order>3</order></author></authors><documents><document><filename>0047957-13122018122315.pdf</filename><originalFilename>LIPIcs-FSTTCS-2018-38.pdf</originalFilename><uploaded>2018-12-13T12:23:15.8570000</uploaded><type>Output</type><contentLength>493769</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-12-13T00:00:00.0000000</embargoDate><documentNotes>Released under the terms of a Creative Commons License (CC-BY).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2019-02-04T08:45:32.1208932 v2 47957 2018-12-13 Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2018-12-13 MACS 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. Conference Paper/Proceeding/Abstract 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) 122 38:1 38:20 FSTTCS 978-3-95977-093-4 1868-8969 31 12 2018 2018-12-31 10.4230/LIPIcs.FSTTCS.2018.38 http://drops.dagstuhl.de/opus/volltexte/2018/9937/ COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2019-02-04T08:45:32.1208932 2018-12-13T11:57:29.6828031 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Stephane Le Roux 1 Arno Pauly 0000-0002-0173-3295 2 Mickael Randour 3 0047957-13122018122315.pdf LIPIcs-FSTTCS-2018-38.pdf 2018-12-13T12:23:15.8570000 Output 493769 application/pdf Version of Record true 2018-12-13T00:00:00.0000000 Released under the terms of a Creative Commons License (CC-BY). true eng
title Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
spellingShingle Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
Arno Pauly
title_short Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
title_full Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
title_fullStr Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
title_full_unstemmed Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
title_sort Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Stephane Le Roux
Arno Pauly
Mickael Randour
format Conference Paper/Proceeding/Abstract
container_title 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
container_volume 122
container_start_page 38:1
publishDate 2018
institution Swansea University
isbn 978-3-95977-093-4
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.FSTTCS.2018.38
publisher FSTTCS
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://drops.dagstuhl.de/opus/volltexte/2018/9937/
document_store_str 1
active_str 0
description 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.
published_date 2018-12-31T05:53:45Z
_version_ 1851280668436201472
score 11.089469

Similar Items