2026-08-17T21:19:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23628 2025-10-27T10:30:23Z ddc:004 open_access

Unifying Boolean and Algebraic Descriptive Complexity Chanus, Baptiste Mazza, Damiano Rogers, Morgan Descriptive complexity theory Categorical logic Blum-Shub-Smale complexity We introduce ultrarings, which simultaneously generalize commutative rings and Boolean lextensive categories. As such, they allow to blend together standard algebraic notions (from commutative algebra) and logical notions (from categorical logic), providing a unifying descriptive framework in which complexity classes over arbitrary rings (as in the Blum, Schub, Smale model) and usual, Boolean complexity classes may be captured in a uniform way. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Baptiste Chanus and Damiano Mazza and Morgan Rogers 2025 Is Part Of LIPIcs, Volume 337, 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2025.13 urn:nbn:de:0030-drops-236286 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode