Show simple item record

dc.contributor.authorPayne, Ian 16:09:34 (GMT) 16:09:34 (GMT)
dc.description.abstractSemilattices are algebras known to have an important connection to partially ordered sets. In particular, if a partially ordered set $(A,\leq)$ has greatest lower bounds, a semilattice $(A;\wedge)$ can be associated to the order where $a\wedge b$ is the greatest lower bound of $a$ and $b$. In this thesis, we study a class of algebras known as 2-semilattices, which is a generalization of the class of semilattices. Similar to the correspondence between partial orders and semilattices, there is a correspondence between certain digraphs and 2-semilattices. That is, to every 2-semilattice, there is an associated digraph which holds information about the 2-semilattice. Making frequent use of this correspondence, we explore the class of 2-semilattices from three perspectives: (i) Tame Congruence Theory, (ii) the ``residual character" of the class of 2-semilattices, and (iii), the constraint satisfaction problem. Tame Congruence Theory, developed in [29], is a structure theory on finite algebras driven by understanding their prime congruence quotients. The theory assigns to each such quotient a type from 1 to 5. We show that types 3, 4, and 5 can occur in the class of 2-semilattices, but type 4 can not occur in a finite simple 2-semilattice. Classes of algebras contain ``subdirectly irreducible" members which hold information about the class. Specifically, the size of these members has been of interest to many authors. We show for certain subclasses of the class of 2-semilattices that there is no cardinal bound on the size of the irreducible members in that subclass. The ``fixed template constraint satisfaction problem" can be identified with the decision problem hom$(\mathbb{A})$ where $\mathbb{A}$ is a fixed finite relational structure. The input to hom$(\mathbb{A})$ is a finite structure $\mathbb{B}$ similar to $\mathbb{A}$. The question asked is ``does there exist a homomorphism from $\mathbb{B}$ to $\mathbb{A}$?" Feder and Vardi [22] conjectured that for fixed $\mathbb{A}$, this decision problem is either NP-complete or solvable in polynomial time. Bulatov [15] confirmed this conjecture in the case that $\mathbb{A}$ is invariant under a 2-semilattice operation. We extend this result.en
dc.publisherUniversity of Waterlooen
dc.title2-Semilattices: Residual Properties and Applications to the Constraint Satisfaction Problemen
dc.typeDoctoral Thesisen
dc.pendingfalse Mathematicsen Mathematicsen of Waterlooen
uws-etd.degreeDoctor of Philosophyen
uws.contributor.advisorWillard, Ross
uws.contributor.affiliation1Faculty of Mathematicsen

Files in this item


This item appears in the following Collection(s)

Show simple item record


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages