Ford M, Milius S, Schröder L (2021)
Publication Type: Conference contribution
Publication year: 2021
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 211
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Virtual, Salzburg, AUT
ISBN: 9783959772129
DOI: 10.4230/LIPIcs.CALCO.2021.14
We introduce a framework for universal algebra in categories of relational structures given by finitary relational signatures and finitary or infinitary Horn theories, with the arity λ of a Horn theory understood as a strict upper bound on the number of premisses in its axioms; key examples include partial orders (λ = ω) or metric spaces (λ = ω1). We establish a bijective correspondence between λ-accessible enriched monads on the given category of relational structures and a notion of λ-ary algebraic theories (i.e. with operations of arity < λ), with the syntax of algebraic theories induced by the relational signature (e.g. inequations or equations-up-to-ϵ). We provide a generic sound and complete derivation system for such relational algebraic theories, thus in particular recovering (extensions of) recent systems of this type for monads on partial orders and metric spaces by instantiation. In particular, we present an ω1-ary algebraic theory of metric completion. The theory-to-monad direction of our correspondence remains true for the case of κ-ary algebraic theories and κ-accessible monads for κ < λ, e.g. for finitary theories over metric spaces.
APA:
Ford, M., Milius, S., & Schröder, L. (2021). Monads on categories of relational structures. In Fabio Gadducci, Alexandra Silva, Alexandra Silva (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Virtual, Salzburg, AUT: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Ford, Matthew, Stefan Milius, and Lutz Schröder. "Monads on categories of relational structures." Proceedings of the 9th Conference on Algebra and Coalgebra in Computer Science, CALCO 2021, Virtual, Salzburg, AUT Ed. Fabio Gadducci, Alexandra Silva, Alexandra Silva, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.
BibTeX: Download