DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.77

Problems with Fixpoints of Polynomials of Polynomials

Authors: Cécilia Pradic and Ian Price

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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 ζ. 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 μ-bicomplete categories, extended with ζ-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.

Cite as

Cécilia Pradic and Ian Price. Problems with Fixpoints of Polynomials of Polynomials. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 77:1-77:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pradic_et_al:LIPIcs.LICS.2026.77,
  author =	{Pradic, C\'{e}cilia and Price, Ian},
  title =	{{Problems with Fixpoints of Polynomials of Polynomials}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{77:1--77:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.77},
  URN =		{urn:nbn:de:0030-drops-268642},
  doi =		{10.4230/LIPIcs.LICS.2026.77},
  annote =	{Keywords: Polynomial functors, containers, fixpoints, Weihrauch complexity}
}

Search Results

Documents authored by Price, Ian

Problems with Fixpoints of Polynomials of Polynomials

Abstract

Cite as

Thanks for your feedback!

Could not send message