TY - GEN
T1 - Unifying Boolean and Algebraic Descriptive Complexity
AU - Chanus, Baptiste
AU - Mazza, Damiano
AU - Rogers, Morgan
N1 - Publisher Copyright:
© Baptiste Chanus, Damiano Mazza, and Morgan Rogers;
PY - 2025/7/7
Y1 - 2025/7/7
N2 - 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.
AB - 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.
KW - Blum-Shub-Smale complexity
KW - Categorical logic
KW - Descriptive complexity theory
UR - https://www.scopus.com/pages/publications/105010697126
U2 - 10.4230/LIPIcs.FSCD.2025.13
DO - 10.4230/LIPIcs.FSCD.2025.13
M3 - Conference contribution
AN - SCOPUS:105010697126
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 10th International Conference on Formal Structures for Computation and Deduction, FSCD 2025
A2 - Fernandez, Maribel
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 10th International Conference on Formal Structures for Computation and Deduction, FSCD 2025
Y2 - 14 July 2025 through 20 July 2025
ER -