No Cover Image

Journal article 923 views 330 downloads

Minkowski Games

Stéphane Le Roux, Arno Pauly Orcid Logo, Jean-François Raskin

ACM Transactions on Computational Logic, Volume: 19, Issue: 3, Pages: 1 - 29

Swansea University Author: Arno Pauly Orcid Logo

Check full text

DOI (Published version): 10.1145/3230741

Abstract

We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety game...

Full description

Published in: ACM Transactions on Computational Logic
ISSN: 1529-3785 1557-945X
Published: Association for Computing Machinery (ACM) 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa40809
first_indexed 2018-06-26T12:03:22Z
last_indexed 2023-01-11T14:17:26Z
id cronfa40809
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-12-05T12:47:36.8161185</datestamp><bib-version>v2</bib-version><id>40809</id><entry>2018-06-25</entry><title>Minkowski Games</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-06-25</date><deptcode>MACS</deptcode><abstract>We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it.We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.</abstract><type>Journal Article</type><journal>ACM Transactions on Computational Logic</journal><volume>19</volume><journalNumber>3</journalNumber><paginationStart>1</paginationStart><paginationEnd>29</paginationEnd><publisher>Association for Computing Machinery (ACM)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1529-3785</issnPrint><issnElectronic>1557-945X</issnElectronic><keywords>game theory; verification of hybrid systems; polytopes</keywords><publishedDay>18</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-09-18</publishedDate><doi>10.1145/3230741</doi><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/><funders/><projectreference/><lastEdited>2022-12-05T12:47:36.8161185</lastEdited><Created>2018-06-25T13:48:55.7611145</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>St&#xE9;phane Le</firstname><surname>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>Jean-Fran&#xE7;ois</firstname><surname>Raskin</surname><order>3</order></author></authors><documents><document><filename>0040809-25062018135152.pdf</filename><originalFilename>1609.07048.pdf</originalFilename><uploaded>2018-06-25T13:51:52.3700000</uploaded><type>Output</type><contentLength>341203</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-06-25T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2022-12-05T12:47:36.8161185 v2 40809 2018-06-25 Minkowski Games 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2018-06-25 MACS We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it.We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable. Journal Article ACM Transactions on Computational Logic 19 3 1 29 Association for Computing Machinery (ACM) 1529-3785 1557-945X game theory; verification of hybrid systems; polytopes 18 9 2018 2018-09-18 10.1145/3230741 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2022-12-05T12:47:36.8161185 2018-06-25T13:48:55.7611145 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Stéphane Le Roux 1 Arno Pauly 0000-0002-0173-3295 2 Jean-François Raskin 3 0040809-25062018135152.pdf 1609.07048.pdf 2018-06-25T13:51:52.3700000 Output 341203 application/pdf Accepted Manuscript true 2018-06-25T00:00:00.0000000 true eng
title Minkowski Games
spellingShingle Minkowski Games
Arno Pauly
title_short Minkowski Games
title_full Minkowski Games
title_fullStr Minkowski Games
title_full_unstemmed Minkowski Games
title_sort Minkowski Games
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Stéphane Le Roux
Arno Pauly
Jean-François Raskin
format Journal article
container_title ACM Transactions on Computational Logic
container_volume 19
container_issue 3
container_start_page 1
publishDate 2018
institution Swansea University
issn 1529-3785
1557-945X
doi_str_mv 10.1145/3230741
publisher Association for Computing Machinery (ACM)
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
document_store_str 1
active_str 0
description We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it.We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.
published_date 2018-09-18T19:35:49Z
_version_ 1821435388661596160
score 11.047609

Similar Items