Philosophiae Doctor - PhD / Categorical closure operators were introduced by Dikranjan and Giuli in [DG87] and then developed by these authors and Tholen in [DGT89]. These operators have played an important role in the development of Categorical Topology by introducing topological concepts, such as connectedness, separatedness and compactness, in an arbitrary category and they provide a uni ed approach to various mathematical notions. Motivated by the theory of these operators, the categorical notion of interior operators was introduced by Vorster in [Vor00]. While there is a notational symmetry between categorical closure and interior operators, a detailed analysis shows that the two operators are not categorically dual to each other, that is: it is not true in general that whatever one does with respect to closure operators may be done relative to interior operators. Indeed, the continuity condition of categorical closure operators can be expressed in terms of images or equivalently, preimages, in the same way as the usual topological closure describes continuity in terms of images or preimages along continuous maps. However, unlike the case of categorical closure operators, the continuity condition of categorical interior operators can not be described in terms of images. Consequently, the general theory of categorical interior operators is not equivalent to the one of closure operators. Moreover, the categorical dual closure operator introduced in [DT15] does not lead to interior operators. As a consequence, the study of categorical interior operators in their own right is interesting.

Constraint programming (CP) is a technology in which a combinatorial problem is modeled declaratively as a conjunction of constraints, each of which captures some of the combinatorial substructure of the problem. Constraints are more than a modeling convenience: every constraint is partially implemented by an inference algorithm, called a propagator, that rules out some but not necessarily all infeasible candidate values of one or more unknowns in the scope of the constraint. Interleaving propagation with systematic search leads to a powerful and complete solution method, combining a high degree of re-usability with natural, high-level modeling. A propagator can be characterized as a sound approximation of a constraint on an abstraction of sets of candidate values; propagators that share an abstraction are similar in the strength of the inference they perform when identifying infeasible candidate values. In this thesis, we consider abstractions of sets of candidate values that may be described by an elegant mathematical formalism, the Galois connection. We develop a theoretical framework from the correspondence between Galois connections and propagators, unifying two disparate views of the abstraction-propagation connection, namely the oft-overlooked distinction between representational and computational over-approximations. Our framework yields compact definitions of propagator strength, even in complicated cases (i.e., involving several types, or unknowns with internal structure); it also yields a method for the principled derivation of propagators from constraint definitions. We apply this framework to the extension of an existing CP solver to constraints over strings, that is, words of finite length. We define, via a Galois connection, an over-approximation for bounded-length strings, and demonstrate two different methods for implementing this overapproximation in a CP solver. First we use the Galois connection to derive a bounded-length string representation as an aggregation of existing scalar types; propagators for this representation are obtained by manual derivation, or automated synthesis, or a combination. Then we implement a string variable type, motivating design choices with knowledge gained from the construction of the over-approximation. The resulting CP solver extension not only substantially eases modeling for combinatorial string problems, but also leads to substantial efficiency improvements over prior CP methods.

<p>In this thesis local methods are made available as a tool to study the<br />unary parts of clones (or, equivalently, the weak Krasner algebras). Using the<br />language of model theory and Galois connections we develop a link between<br />homomorphism-homogeneous relational structures and local methods, via the<br />notion of endolocality. The theoretical results that are obtained are used to develop<br />a systematic theory for the classification of homomorphism-homogeneous<br />relational structures.</p> / <p>U ovoj tezi su razvijene lokalne metode koje se mogu koristiti za izu-<br />ˇcavanje unarnih delova klonova (ili, ekvivalentno, slabih Krasnerovih algebri).<br />Koriˇs&acute;cenjem jezika teorije modela i Galoovih veza uspostavljen je odnos izmedu<br />homomorfizam-homogenih relacionih struktura i lokalnih metoda, preko pojma<br />endolokalnosti. Dobijeni teoretski rezultati su upotrebljeni za razvoj sistematske<br />teorije za klasifikaciju homomorfizam-homogenih struktura.</p>