No Cover Image

Conference Paper/Proceeding/Abstract 761 views 104 downloads

Parameterized Games and Parameterized Automata

Arno Pauly Orcid Logo

Electronic Proceedings in Theoretical Computer Science, Volume: 277, Pages: 30 - 42

Swansea University Author: Arno Pauly Orcid Logo

Check full text

DOI (Published version): 10.4204/EPTCS.277.3

Abstract

We introduce a way to parameterize automata and games on finite graphs with natural numbers. The parameters are accessed essentially by allowing counting down from the parameter value to 0 and branching depending on whether 0 has been reached. The main technical result is that in games, a player can...

Full description

Published in: Electronic Proceedings in Theoretical Computer Science
ISSN: 2075-2180
Published: 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa46098
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2018-11-26T14:23:17Z
last_indexed 2018-12-13T14:07:38Z
id cronfa46098
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2018-12-13T11:54:51.2959595</datestamp><bib-version>v2</bib-version><id>46098</id><entry>2018-11-26</entry><title>Parameterized Games and Parameterized Automata</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-11-26</date><deptcode>SCS</deptcode><abstract>We introduce a way to parameterize automata and games on finite graphs with natural numbers. The parameters are accessed essentially by allowing counting down from the parameter value to 0 and branching depending on whether 0 has been reached. The main technical result is that in games, a player can win for some values of the parameters at all, if she can win for some values below an exponential bound. For many winning conditions, this implies decidability of any statements about a player being able to win with arbitrary quantification over the parameter values.While the result seems broadly applicable, a specific motivation comes from the study of chains of strategies in games. Chains of games were recently suggested as a means to define a rationality notion based on dominance that works well with quantitative games by Bassett, Jecker, P., Raskin and Van den Boogard. From the main result of this paper, we obtain generalizations of their decidability results with much simpler proofs.As both a core technical notion in the proof of the main result, and as a notion of potential independent interest, we look at boolean functions defined via graph game forms. Graph game forms have properties akin to monotone circuits, albeit are more concise. We raise some open questions regarding how concise they are exactly, which have a flavour similar to circuit complexity. Answers to these questions could improve the bounds in the main theorem.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Electronic Proceedings in Theoretical Computer Science</journal><volume>277</volume><paginationStart>30</paginationStart><paginationEnd>42</paginationEnd><publisher/><issnElectronic>2075-2180</issnElectronic><keywords/><publishedDay>7</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-09-07</publishedDate><doi>10.4204/EPTCS.277.3</doi><url>http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF18.3</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2018-12-13T11:54:51.2959595</lastEdited><Created>2018-11-26T11:15:37.4085239</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>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>1</order></author></authors><documents><document><filename>0046098-26112018112133.pdf</filename><originalFilename>46098.pdf</originalFilename><uploaded>2018-11-26T11:21:33.7070000</uploaded><type>Output</type><contentLength>165767</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-11-25T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2018-12-13T11:54:51.2959595 v2 46098 2018-11-26 Parameterized Games and Parameterized Automata 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2018-11-26 SCS We introduce a way to parameterize automata and games on finite graphs with natural numbers. The parameters are accessed essentially by allowing counting down from the parameter value to 0 and branching depending on whether 0 has been reached. The main technical result is that in games, a player can win for some values of the parameters at all, if she can win for some values below an exponential bound. For many winning conditions, this implies decidability of any statements about a player being able to win with arbitrary quantification over the parameter values.While the result seems broadly applicable, a specific motivation comes from the study of chains of strategies in games. Chains of games were recently suggested as a means to define a rationality notion based on dominance that works well with quantitative games by Bassett, Jecker, P., Raskin and Van den Boogard. From the main result of this paper, we obtain generalizations of their decidability results with much simpler proofs.As both a core technical notion in the proof of the main result, and as a notion of potential independent interest, we look at boolean functions defined via graph game forms. Graph game forms have properties akin to monotone circuits, albeit are more concise. We raise some open questions regarding how concise they are exactly, which have a flavour similar to circuit complexity. Answers to these questions could improve the bounds in the main theorem. Conference Paper/Proceeding/Abstract Electronic Proceedings in Theoretical Computer Science 277 30 42 2075-2180 7 9 2018 2018-09-07 10.4204/EPTCS.277.3 http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF18.3 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2018-12-13T11:54:51.2959595 2018-11-26T11:15:37.4085239 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arno Pauly 0000-0002-0173-3295 1 0046098-26112018112133.pdf 46098.pdf 2018-11-26T11:21:33.7070000 Output 165767 application/pdf Version of Record true 2018-11-25T00:00:00.0000000 true eng
title Parameterized Games and Parameterized Automata
spellingShingle Parameterized Games and Parameterized Automata
Arno Pauly
title_short Parameterized Games and Parameterized Automata
title_full Parameterized Games and Parameterized Automata
title_fullStr Parameterized Games and Parameterized Automata
title_full_unstemmed Parameterized Games and Parameterized Automata
title_sort Parameterized Games and Parameterized Automata
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Arno Pauly
format Conference Paper/Proceeding/Abstract
container_title Electronic Proceedings in Theoretical Computer Science
container_volume 277
container_start_page 30
publishDate 2018
institution Swansea University
issn 2075-2180
doi_str_mv 10.4204/EPTCS.277.3
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://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF18.3
document_store_str 1
active_str 0
description We introduce a way to parameterize automata and games on finite graphs with natural numbers. The parameters are accessed essentially by allowing counting down from the parameter value to 0 and branching depending on whether 0 has been reached. The main technical result is that in games, a player can win for some values of the parameters at all, if she can win for some values below an exponential bound. For many winning conditions, this implies decidability of any statements about a player being able to win with arbitrary quantification over the parameter values.While the result seems broadly applicable, a specific motivation comes from the study of chains of strategies in games. Chains of games were recently suggested as a means to define a rationality notion based on dominance that works well with quantitative games by Bassett, Jecker, P., Raskin and Van den Boogard. From the main result of this paper, we obtain generalizations of their decidability results with much simpler proofs.As both a core technical notion in the proof of the main result, and as a notion of potential independent interest, we look at boolean functions defined via graph game forms. Graph game forms have properties akin to monotone circuits, albeit are more concise. We raise some open questions regarding how concise they are exactly, which have a flavour similar to circuit complexity. Answers to these questions could improve the bounds in the main theorem.
published_date 2018-09-07T03:57:49Z
_version_ 1763752929902198784
score 11.013148

Similar Items