Fuzzy Algebraic Theories and M,N-adhesive categories

This thesis deals with two quite unrelated subjects in Computer Science: one is the relationship between algebraic theories and monads, the other one is the study of adhesivity properties of categories. The first part of the thesis begins by revisiting some basic facts regarding monads. Specifically, we review the correspondence between monads, with rank, on the category of sets and functions, and algebraic theories in which the operations’ arity is bounded by some regular cardinal. Next, we move to the heart of this part of the thesis: the extension of this correspondence to the category Fuz(H) of fuzzy sets. This result is obtained by means of a formal system for fuzzy algebraic reasoning. We define a sequent calculus based on two types of propositions: those that establish the equality of terms, and those that assert the membership degree of such terms. We establish a sound semantics for this calculus, and demonstrate the existence of a notion of free model for any theory in the system. This, in turn, allows us, to prove a completeness result: a formula is derivable from a given theory if and only if it is satisfied by all models of the theory. Moreover, we also prove that, under certain restrictions, it is possible to recover models of a given theory as Eilenberg-Moore algebras for a monad on Fuz(H). Finally, leveraging the work of Milius and Urbat, we provide a HSP-like characterizations of subcategories of algebras that are categories of models of specific types of theories. The second part of the thesis is devoted to the study of adhesivity properties of various categories. Adhesive and quasiadhesive categories, and other generalizations such as M,N-adhesive ones, marked a watershed moment for the algebraic approaches to the rewriting of graph-like structures, since they provide an abstract framework where many general results (on, e.g., parallelism) could be recast and uniformly proved. However, often checking that a model satisfies the adhesivity properties is far from immediate. After having recalled, the basic definitions, we present a new criterion giving a sufficient condition for M,N-adhesivity. It is known that in a quasiadhesive category the join of any two regular subobjects is also a regular subobject. Conversely, if regular monomorphisms are adhesive, the existence of a regular join for every pair of regular subobjects implies quasiadhesivity. Furthermore, (quasi)adhesive categories can be embedded in a Grothendieck topos via a functor that preserves pullbacks and pushouts along (regular) monomorphisms. In this paper, we extend these results to M,N-adhesive categories. To achieve this, we introduce the concept of an N-(pre)adhesive morphism, which enables us to express M,N-adhesivity as a condition on the poset of subobjects. Additionally, N-adhesive morphisms allow us to demonstrate how a M,N-adhesive category can be embedded into a Grothendieck topos, preserving pullbacks and M,N-pushouts. Finally, we exploit the previous results to establish adhesivity properties of several existing categories of graph-like structures, including hypergraphs, various kinds of hierarchical graphs (a formalism that is notoriously difficult to fit in the mould of algebraic approaches to rewriting), and combinations of them.