No Cover Image

Journal article 793 views 96 downloads

Game characterizations and lower cones in the Weihrauch degrees

Hugo Nobrega, Arno Pauly Orcid Logo

Logical Methods in Computer Science, Volume: 15, Issue: 3, Pages: 1 - 29

Swansea University Author: Arno Pauly Orcid Logo

  • 1511.03693.pdf

    PDF | Version of Record

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

    Download (533.48KB)

Check full text

DOI (Published version): 10.23638/LMCS-15(3:11)2019

Abstract

We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particula...

Full description

Published in: Logical Methods in Computer Science
ISSN: 1860-5974
Published: 2019
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa51342
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2019-08-09T16:32:06Z
last_indexed 2019-08-16T15:30:14Z
id cronfa51342
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2019-08-16T13:17:57.0956967</datestamp><bib-version>v2</bib-version><id>51342</id><entry>2019-08-07</entry><title>Game characterizations and lower cones in the Weihrauch degrees</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>2019-08-07</date><deptcode>SCS</deptcode><abstract>We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on which classes of functions admit game characterizations. We then discuss some applications of such parametrized Wadge games. Using machinery from Weihrauch reducibility theory, we introduce games characterizing every (transfinite) level of the Baire hierarchy via an iteration of a pruning derivative on countably branching trees.</abstract><type>Journal Article</type><journal>Logical Methods in Computer Science</journal><volume>15</volume><journalNumber>3</journalNumber><paginationStart>1</paginationStart><paginationEnd>29</paginationEnd><publisher/><issnElectronic>1860-5974</issnElectronic><keywords/><publishedDay>5</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-08-05</publishedDate><doi>10.23638/LMCS-15(3:11)2019</doi><url>https://lmcs.episciences.org/5670</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2019-08-16T13:17:57.0956967</lastEdited><Created>2019-08-07T13:24:33.7638863</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>Hugo</firstname><surname>Nobrega</surname><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>2</order></author></authors><documents><document><filename>0051342-07082019132620.pdf</filename><originalFilename>1511.03693.pdf</originalFilename><uploaded>2019-08-07T13:26:20.7630000</uploaded><type>Output</type><contentLength>495009</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><embargoDate>2019-08-07T00:00:00.0000000</embargoDate><documentNotes>Released under the terms of a Creative Commons Attribution License (CC-BY).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2019-08-16T13:17:57.0956967 v2 51342 2019-08-07 Game characterizations and lower cones in the Weihrauch degrees 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2019-08-07 SCS We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on which classes of functions admit game characterizations. We then discuss some applications of such parametrized Wadge games. Using machinery from Weihrauch reducibility theory, we introduce games characterizing every (transfinite) level of the Baire hierarchy via an iteration of a pruning derivative on countably branching trees. Journal Article Logical Methods in Computer Science 15 3 1 29 1860-5974 5 8 2019 2019-08-05 10.23638/LMCS-15(3:11)2019 https://lmcs.episciences.org/5670 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2019-08-16T13:17:57.0956967 2019-08-07T13:24:33.7638863 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Hugo Nobrega 1 Arno Pauly 0000-0002-0173-3295 2 0051342-07082019132620.pdf 1511.03693.pdf 2019-08-07T13:26:20.7630000 Output 495009 application/pdf Version of Record true 2019-08-07T00:00:00.0000000 Released under the terms of a Creative Commons Attribution License (CC-BY). true eng
title Game characterizations and lower cones in the Weihrauch degrees
spellingShingle Game characterizations and lower cones in the Weihrauch degrees
Arno Pauly
title_short Game characterizations and lower cones in the Weihrauch degrees
title_full Game characterizations and lower cones in the Weihrauch degrees
title_fullStr Game characterizations and lower cones in the Weihrauch degrees
title_full_unstemmed Game characterizations and lower cones in the Weihrauch degrees
title_sort Game characterizations and lower cones in the Weihrauch degrees
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Hugo Nobrega
Arno Pauly
format Journal article
container_title Logical Methods in Computer Science
container_volume 15
container_issue 3
container_start_page 1
publishDate 2019
institution Swansea University
issn 1860-5974
doi_str_mv 10.23638/LMCS-15(3:11)2019
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 https://lmcs.episciences.org/5670
document_store_str 1
active_str 0
description We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on which classes of functions admit game characterizations. We then discuss some applications of such parametrized Wadge games. Using machinery from Weihrauch reducibility theory, we introduce games characterizing every (transfinite) level of the Baire hierarchy via an iteration of a pruning derivative on countably branching trees.
published_date 2019-08-05T04:03:12Z
_version_ 1763753267930595328
score 11.035634

Similar Items