No Cover Image

Conference Paper/Proceeding/Abstract 5 views

Problems with fixpoints of polynomials of polynomials

Cécilia Pradic Orcid Logo, Ian Price

Logic in Computer Science 2026

Swansea University Authors: Cécilia Pradic Orcid Logo, Ian Price

Abstract

Motivated by applications in computable analysis, we study fixpoints of certain endofunctors over categories of containers. More specifically, we focus on fibred endofunctors over the fibrewise opposite of the codomain fibration that can be themselves be represented by families of polynomial endofun...

Full description

Published in: Logic in Computer Science 2026
Published: Lipics
Online Access: https://arxiv.org/abs/2601.15420
URI: https://cronfa.swan.ac.uk/Record/cronfa71916
first_indexed 2026-05-15T16:23:58Z
last_indexed 2026-05-16T05:23:16Z
id cronfa71916
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2026-05-15T17:23:56.5755314</datestamp><bib-version>v2</bib-version><id>71916</id><entry>2026-05-15</entry><title>Problems with fixpoints of polynomials of polynomials</title><swanseaauthors><author><sid>3b6e9ebd791c875dac266b3b0b358a58</sid><ORCID>0000-0002-1600-8846</ORCID><firstname>C&#xE9;cilia</firstname><surname>Pradic</surname><name>C&#xE9;cilia Pradic</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>bdc2b56a25bb7272cbbfdb189e5402d6</sid><ORCID/><firstname>Ian</firstname><surname>Price</surname><name>Ian Price</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2026-05-15</date><deptcode>MACS</deptcode><abstract>Motivated by applications in computable analysis, we study fixpoints of certain endofunctors over categories of containers. More specifically, we focus on fibred endofunctors over the fibrewise opposite of the codomain fibration that can be themselves be represented by families of polynomial endofunctors. In this setting, we show how to compute initial algebras, terminal coalgebras and another kind of fixpoint &#x3B6;. We then explore a number of examples of derived operators inspired by Weihrauch complexity and the usual construction of the free polynomial monad.We introduce &#x3B6;-expressions as the syntax of \mu-bicomplete categories, extended with \zeta-binders and parallel products, which thus have a natural denotation in containers. By interpreting certain &#x3B6;-expressions in a category of type 2 computable maps, we are able to capture a number of meaningful Weihrauch degrees, ranging from closed choice on {0, 1} to determinacy of infinite parity games, via an "answerable part" operator.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Logic in Computer Science 2026</journal><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher>Lipics</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords/><publishedDay>0</publishedDay><publishedMonth>0</publishedMonth><publishedYear>0</publishedYear><publishedDate>0001-01-01</publishedDate><doi/><url>https://arxiv.org/abs/2601.15420</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>Not Required</apcterm><funders/><projectreference/><lastEdited>2026-05-15T17:23:56.5755314</lastEdited><Created>2026-05-15T17:13:43.3425818</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>C&#xE9;cilia</firstname><surname>Pradic</surname><orcid>0000-0002-1600-8846</orcid><order>1</order></author><author><firstname>Ian</firstname><surname>Price</surname><orcid/><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2026-05-15T17:23:56.5755314 v2 71916 2026-05-15 Problems with fixpoints of polynomials of polynomials 3b6e9ebd791c875dac266b3b0b358a58 0000-0002-1600-8846 Cécilia Pradic Cécilia Pradic true false bdc2b56a25bb7272cbbfdb189e5402d6 Ian Price Ian Price true false 2026-05-15 MACS Motivated by applications in computable analysis, we study fixpoints of certain endofunctors over categories of containers. More specifically, we focus on fibred endofunctors over the fibrewise opposite of the codomain fibration that can be themselves be represented by families of polynomial endofunctors. In this setting, we show how to compute initial algebras, terminal coalgebras and another kind of fixpoint ζ. We then explore a number of examples of derived operators inspired by Weihrauch complexity and the usual construction of the free polynomial monad.We introduce ζ-expressions as the syntax of \mu-bicomplete categories, extended with \zeta-binders and parallel products, which thus have a natural denotation in containers. By interpreting certain ζ-expressions in a category of type 2 computable maps, we are able to capture a number of meaningful Weihrauch degrees, ranging from closed choice on {0, 1} to determinacy of infinite parity games, via an "answerable part" operator. Conference Paper/Proceeding/Abstract Logic in Computer Science 2026 Lipics 0 0 0 0001-01-01 https://arxiv.org/abs/2601.15420 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Not Required 2026-05-15T17:23:56.5755314 2026-05-15T17:13:43.3425818 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Cécilia Pradic 0000-0002-1600-8846 1 Ian Price 2
title Problems with fixpoints of polynomials of polynomials
spellingShingle Problems with fixpoints of polynomials of polynomials
Cécilia Pradic
Ian Price
title_short Problems with fixpoints of polynomials of polynomials
title_full Problems with fixpoints of polynomials of polynomials
title_fullStr Problems with fixpoints of polynomials of polynomials
title_full_unstemmed Problems with fixpoints of polynomials of polynomials
title_sort Problems with fixpoints of polynomials of polynomials
author_id_str_mv 3b6e9ebd791c875dac266b3b0b358a58
bdc2b56a25bb7272cbbfdb189e5402d6
author_id_fullname_str_mv 3b6e9ebd791c875dac266b3b0b358a58_***_Cécilia Pradic
bdc2b56a25bb7272cbbfdb189e5402d6_***_Ian Price
author Cécilia Pradic
Ian Price
author2 Cécilia Pradic
Ian Price
format Conference Paper/Proceeding/Abstract
container_title Logic in Computer Science 2026
institution Swansea University
publisher Lipics
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://arxiv.org/abs/2601.15420
document_store_str 0
active_str 0
description Motivated by applications in computable analysis, we study fixpoints of certain endofunctors over categories of containers. More specifically, we focus on fibred endofunctors over the fibrewise opposite of the codomain fibration that can be themselves be represented by families of polynomial endofunctors. In this setting, we show how to compute initial algebras, terminal coalgebras and another kind of fixpoint ζ. We then explore a number of examples of derived operators inspired by Weihrauch complexity and the usual construction of the free polynomial monad.We introduce ζ-expressions as the syntax of \mu-bicomplete categories, extended with \zeta-binders and parallel products, which thus have a natural denotation in containers. By interpreting certain ζ-expressions in a category of type 2 computable maps, we are able to capture a number of meaningful Weihrauch degrees, ranging from closed choice on {0, 1} to determinacy of infinite parity games, via an "answerable part" operator.
published_date 0001-01-01T06:23:16Z
_version_ 1865321279812272128
score 11.105427

Similar Items