We introduce a special set of relations on a finite set, called clausal relations. A restricted version of the Galois connection between polymorphisms and invariants, called Pol-CInv, is studied, where the invariant relations are clausal relations. Clones arising from this Galois connection, so-called C-clones, are investigated. Finally, we show that clausal relations meet a sufficient condition that is known to ensure polynomial time solvability of the corresponding CSP.

We introduce a special set of relations on a finite set, called clausal relations. A restricted version of the Galois connection between polymorphisms and invariants, called Pol-CInv, is studied, where the invariant relations are clausal relations. Clones arising from this Galois connection, so-called C-clones, are investigated. Finally, we show that clausal relations meet a sufficient condition that is known to ensure polynomial time solvability of the corresponding CSP.

Constraint satisfaction problems (CSPs) form a large class of decision problems that con- tains numerous classical problems like the satisfiability problem for propositional formulas and the graph colourability problem. Feder and Vardi [52] gave the following logical for- malization of the class of CSPs: every finite relational structure A, the template, gives rise to the decision problem of determining whether there exists a homomorphism from a finite input structure B to A. In their seminal paper, Feder and Vardi recognised that CSPs had a particular status in the landscape of computational complexity: despite the generality of these problems, it seemed impossible to construct NP-intermediate problems `a la Ladner [72] within this class. The authors thus conjectured that the class of CSPs satisfies a complexity dichotomy , i.e., that every CSP is solvable in polynomial time or is NP-complete. The Feder-Vardi dichotomy conjecture was the motivation of an intensive line of research over the last two decades. Some of the landmarks of this research are the confirmation of the conjecture for special classes of templates, e.g., for the class of undi- rected graphs [55], for the class of smooth digraphs [5], and for templates with at most three elements [43, 84]. Finally, after being open for 25 years, Bulatov [44] and Zhuk [87] independently proved that the conjecture of Feder and Vardi indeed holds. The success of the research program on the Feder-Vardi conjecture is based on the con- nection between constraint satisfaction problems and universal algebra. In their seminal paper, Feder and Vardi described polynomial-time algorithms for CSPs whose template satisfies some closure properties. These closure properties are properties of the polymor- phism clone of the template and similar properties were later used to provide tractability or hardness criteria [61, 62]. Shortly thereafter, Bulatov, Jeavons, and Krokhin [46] proved that the complexity of the CSP depends only on the equational properties of the poly- morphism clone of the template. They proved that trivial equational properties imply hardness of the CSP, and conjectured that the CSP is solvable in polynomial time if the polymorphism clone of the template satisfies some nontrivial equation. It is this conjecture that Bulatov and Zhuk finally proved, relying on recent developments in universal algebra. As a by-product of the fact that the delineation between polynomial-time tractability and NP-hardness can be stated algebraically, we also obtain that the meta-problem for finite- domain CSPs is decidable. That is, there exists an algorithm that, given a finite relational structure A as input, decides the complexity of the CSP of A.

Achieving a classification of all clones of operations over a finite set is one of the goals at the heart of universal algebra. In 1921 Post provided a full description of the lattice of all clones over a two-element set. However, over the following years, it has been shown that a similar classification seems arduously reachable even if we only focus on clones over three-element sets: in 1959 Janov and Mučnik proved that there exists a continuum of clones over a k-element set for every k > 2. Subsequent research in universal algebra therefore focused on understanding particular aspects of clone lattices over finite domains. Remarkable results in this direction are the description of maximal and minimal clones. One might still hope to classify all operation clones on finite domains up to some equivalence relation so that equivalent clones share many of the properties that are of interest in universal algebra. In a recent turn of events, a weakening of the notion of clone homomorphism was introduced: a minor-preserving map from a clone C to D is a map which preserves arities and composition with projections. The minor-equivalence relation on clones over finite sets gained importance both in universal algebra and in computer science: minor-equivalent clones satisfy the same set identities of the form f(x_1,...,x_n) = g(y_1,...,y_m), also known as minor-identities. Moreover, it was proved that the complexity of the CSP of a finite structure A only depends on the set of minor-identities satisfied by the polymorphism clone of A. Throughout this dissertation we focus on the poset that arises by considering clones over a three-element set with the following order: we write C ≤_{m} D if there exist a minor-preserving map from C to D. It has been proved that ≤_{m} is a preorder; we call the poset arising from ≤_{m} the pp-constructability poset. We initiate a systematic study of the pp-constructability poset. To this end, we distinguish two cases that are qualitatively distinct: when considering clones over a finite set A, one can either set a boundary on the cardinality of A, or not. We denote by P_n the pp-constructability poset restricted to clones over a set A such that |A|=n and by P_{fin} we denote the whole pp-constructability poset, i.e., we only require A to be finite. First, we prove that P_{fin} is a semilattice and that it has no atoms. Moreover, we provide a complete description of P_2 and describe a significant part of P_3: we prove that P_3 has exactly three submaximal elements and present a full description of the ideal generated by one of these submaximal elements. As a byproduct, we prove that there are only countably many clones of self-dual operations over {0,1,2} up to minor-equivalence.

Die progrediente, muskuloskelettale Erkrankung Ostheoarthrose wird aufgrund der immer älter werdenden Weltbevölkerung im Jahre 2020 einer der häufigsten Invaliditätsgründe sein. Koelling et al. beschrieb 2009 eine migrierende, chondrogene Progenitorzelllinie (CPC) im Reparaturgewebe der fortgeschrittenen Gonarthrose des Menschen, die Stammzelleigenschaften besitzt. Sie sind multipotent, klonal und besitzen ein osteochondrogenes Expressionsmuster, wodurch sie sich für neue Behandlungsmöglichkeiten bei der Ostheoarthrosetherapie eignen könnten. In dieser Arbeit wurden in vitro drei Klone einer humanen CPC-Population aus osteoarthrotisch verändertem Knorpel hinsichtlich ihrer multipotenten Eigenschaften, Proliferationsgeschwindigkeit und unterschiedlicher Phänotypen gegenübergestellt, da sich bei anderen Stammzelllinien Zusammenhänge zwischen diesen Eigenschaften zeigen, die mit fortgeschrittener Ausdifferenzierung der Stammzellen begründet wird. Die drei Klone IF-8, IIB-6 und IID-4 wurden 12 Tage unter Standardbedingungen in 2D-Flaschenkultur gehalten und anschließend ihr normaler Phänotyp ausgewertet. Dabei zeigte sich, dass IF-8 und IIB-6 eher einen fibroblastenartigen Phänotyp ausbildeten, während sich bei IID-4 erst kugelige Zellen bildeten, die später teils in eine längliche Form übergingen. Die fibroblastenartige Form entsprach der von CPCs aus heterogenen Kulturen, wohingegen der Phänotyp von IID-4 auf Dedifferenzierung oder fortgeschrittenere Differenzierung schließen ließ. Die Klone für die Differenzierungsversuche wurden mit zwei verschiedenen Zelldichten ausgesät, um auch eventuelle Einflüsse der Zelldichte mit in die Untersuchung einzubeziehen. Es wurde pro Well einmal die Anfangskonzentration von 1000 Zellen gewählt und einmal 3000 Zellen pro Well. Nach sechs Tagen wurden morphologische Veränderungen unter dem Mikroskop ausgewertet. Die Differenzierung in Adipozyten und Osteoblasten erfolgte insgesamt über zehn Tage mit anschließendem Differenzie- rungsnachweis mittels Oil-Red-Färbung von Adipozyten, bzw. der Alkalischen-Phosphatase-Reaktion der Osteoblasten. Es wurde zusätzlich mit der Immunfluoreszenzzytochemie kontrolliert, ob in den differenzierten Zellen auch spezifische Proteine exprimiert wurden und sich zwischen den Klonen ein quantitativer Unterschied ergibt, der auf einen veränderten Differenzierungsgrad der Klone schließen konnte. Für die Adipozyten wurden Antikörper gegen dieLipoproteinlipase und PPARγ gewählt, bei den Osteoblasten kamen Antikörper gegen Osteocalcin und den osteogenen Transkriptionsfaktor runx-2 zum Einsatz. Allen Differenzierungsversuchen wurden jeweils Kontrollgruppen gegenübergestellt. Die Ergebnisse zeigten morphologische Unterschiede zwischen den Klonen und den verschiedenen Zelldichten, die bei der osteogenen Differenzierung nicht so stark ausgeprägt waren wie bei der adipogenen. Der Klon-IID-4 zeigte auch hier die am Stärksten ausgeprägtesten morphologischen Unterschiede zwischen den Zellen selber und der verschiedenen Dichtegrade. Die quantitative Auswertung mittels Oil-Red und Alkalischer-Phosphatase, bzw. die Ergebnisse der Immunzytochemie ergaben hingegen keine Abweichungen zwischen den Klonen und keine Veränderung in Abhängigkeit zur Zelldichte. Dadurch konnte gezeigt werden, dass bei den CPCs ein veränderter Phänotyp kein Hinweis auf eine fortgeschrittene Zellalterung und verminderte Differenzierbarkeit ist. Auch die Zelldichte nimmt auf die Differenzierung in andere Zelllinien keinen positiven oder negativen Einfluss. Deutliche Unterschiede zwischen den Klonen zeigten sich hinsichtlich ihrer Proliferationsgeschwindigkeit und ihres osteochondrogenen Grundmusters. Für das Proliferationsassay wurden über den Zeitraum von sieben Tagen die Zellzahlen gemessen. Dabei wurde festgestellt, dass sich Klon-IF-8 am langsamsten teilte, danach folgte IID-4 und am Ende IIB-6. Im Zusammenhang mit dem Western-Blot, bei dem der osteogene Transkriptionsfaktor runx-2 und der chondrogene Transkrip-tionsfaktor sox-9 miteinander verglichen wurden, konnte eine Beziehung zwischen Proliferationsgeschwindigkeit und der Ausprägung der Transkriptionsfaktoren festgestellt werden. Mit Abnahme der Proliferationsgeschwindigkeit nimmt die Expression von runx-2 zu, während die Expression von sox-9 abnimmt. Dadurch konnte nachgewiesen werden, dass die CPCs mit abnehmender Zellteilung in einen vermehrt osteogenen Zustand übergehen und ihren osteochondrogenen Charakter verlieren. Dieser Übergang hat jedoch keinen Einfluss auf ihre multipotenten Eigenschaften. Mit den Ergebnissen konnte gezeigt werden, dass sich CPCs, ähnlich wie andere Progenitorzellen auch, in ihrer Entwicklung weiter ausdifferenzieren und sich dadurch innerhalb einer Population verschiedene Entwicklungszustände ergeben, die eine genauere Charakterisierung der CPCs weiter erschweren.

In this thesis, we generalize clones (as well as their relational counterparts and the relationship between them) to categories. Based on this framework, we introduce a general duality theory for clones and apply it to obtain new results for clones on finite sets.

In this thesis, we generalize clones (as well as their relational counterparts and the relationship between them) to categories. Based on this framework, we introduce a general duality theory for clones and apply it to obtain new results for clones on finite sets.

HINTERGRUND: Die Reaktivierung des Humanen Cytomegalievirus (HCMV) ist immer noch eine häufige Ursache für Morbidität und Mortalität unter immunsupprimierten Patienten. Eine effiziente T-Zell-Antwort vermag die unkontrollierte Ausbreitung des Virus zu verhindern. Vieles über diese T-Zell-Antwort ist aber noch unklar. Im Rahmen dieser Studie wurden daher bei HCMV-seropositiven herz- (n = 17) und lungentransplantierten (n = 3) Patienten Epitope in zwei wichtigen T-Zell-Zielen, den HCMV-Proteinen IE-1 (UL123) und pp65 (UL83), identifiziert, die Frequenzen der für diese Epitope spezifischen T-Zellen gemessen und die Klonalität ausgewählter starker CD8+ T-Zell-Antworten untersucht. METHODEN: Dazu wurden Pentadecapeptide, die die gesamte Aminosäure-Sequenz von IE-1 bzw. pp65 umfassten und sich um jeweils 11 Aminosäurereste überlappten, in Pools von 25 bis 30 Peptiden so zusammengefasst, dass jedes Peptid in einer einzigartigen Kombination von drei Pools enthalten war. PBMC der Patienten wurden dann mit den Peptid-Pools stimuliert und die resultierenden T-Zell-Reaktionen durch Färbung von intrazellulär zurückgehaltenem Interferon-gamma durchflusszytometrisch sichtbar gemacht. Immunogene Peptide konnten anhand der jeweiligen drei Pools, die zu IFN-gamma-Produktion führten, eindeutig identifiziert werden. Einige dieser T-Zell-Populationen wurden durch einen IFN-gamma-Sekretions-Assay, magnetische Zellseparation und durchflusszytometrische Feinsortierung aus PBMC isoliert und ihre Klonalität mit Hilfe einer Polymerase-Kettenreaktion zum Nachweis klonal expandierter gamma-T-Zell-Rezeptor-Rearrangements (TCR-PCR) und anschliessender Fragmentanalyse fluoreszenzmarkierter PCR-Amplifikate untersucht. ERGEBNISSE: Bei den Patienten bestanden grosse Unterschiede hinsichtlich des jeweils immundominanten Proteins, der Dominanz von CD4+ bzw. CD8+ T-Zell-Subpopulation, der antigenen Determinanten, der gemessenen Peptid-spezifischen T-Zell-Frequenzen sowie der Anzahl der identifizierten Epitope. Zehn zuvor noch nicht beschriebene Epitope wurden eben-falls identifiziert und die präsentierenden HLA-Allele der meisten in der Patientengruppe identifizierten Epitope bestimmt. Die mittels TCR-PCR untersuchten CD8+ T-Zell-Reaktionen waren auf einen oder wenige Klone fokussiert. Die Korrelation der experimentellen Daten mit den klinischen Verläufen der Patienten hinsichtlich HCMV-Reaktivierung und -Erkrankung erbrachte jedoch keine Hinweise auf einen konkreten Zusammenhang. SCHLUSSFOLGERUNGEN: Zusammenfassend ermöglichen die hier vorgestellten Methoden die Untersuchung des Langzeitverlaufes der CD4+ und CD8+ T-Zell-Antwort gegen immundominante Proteine auf Epitop-Ebene nach initialer Identifizierung der antigenen Determinanten, die direkte Bestimmung der Frequenzen der Epitop-spezifischen T-Zellen sowie die Untersuchung der Klonalität dieser Reaktionen aus ca. 2 x 20 ml Blut. Die Langzeit-Untersuchung von Patienten mit hohem Risiko für HCMV-Reaktivierung und -Erkrankung kann so zu einem besseren Verständnis der komplexen HCMV-spezifischen T-Zell-Anwort und damit möglicherweise auch zur Verbesserung von Diagnose, Prophylaxe und Therapie dieser Patienten beitragen. / BACKGROUND: Human cytomegalovirus (HCMV) reactivation is still a leading cause of morbidity and mortality among immunosuppressed patients. Uncontrolled viral spread is prevented by an efficient T-cell response. However, little is known about the nature of this T-cell response. In this study we identified epitopes in two immunodominant HCMV-proteins, IE-1 (UL123) and pp65 (UL83), measured the frequencies of T-cells specific for these, and studied the clonotypic composition of selected T-cell responses in a group of HCMV-seropositive heart (n = 17) and lung (n = 3) transplant patients. METHODS: For both proteins overlapping pentadecapeptides covering the entire respective amino acid sequences were arranged in pools of 25 peptides each in such a way that every peptide was contained in exactly 3 pools. PBMC were stimulated with the resulting 15 pools for IE-1 or 16 pools or pp65, respectively, as well as with pools containing all peptides of the corresponding protein. Individual peptides leading to a positive T-cell response were identified by flow cytometric detection of intracellular interferon-gamma, each single peptide corresponding to a unique combination of 3 peptide pools. Selected T-cell populations specific for the previously identified single peptides were purified by performing an IFN-gamma secretion assay prior to magnetic cell separation and subsequent fluorescence-activated cell sorting. The clonality of these highly purified peptide-specific T-cell populations was then investigated by a T-cell receptor-gamma rearrangement-PCR and subsequent fragment analysis of fluorescence-labelled PCR amplificates. RESULTS: We observed broad heterogeneity among the patients in terms of the immunodominant protein, number of epitopes, predominance of CD4 or CD8 T-cell responses, and epitope-specific T-cell frequencies. 10 previously unknown epitopes were identified, and the HLA-restriction of most of the identified epitopes could be determined. The investigated T-cell responses showed a high degree of clonal focussing. These data were correlated to the patients episodes of HCMV reactivation, but a correlation between differences in the T-cell responses and a different clinical outcome in terms of HCMV-reactivation could not be established. CONCLUSIONS: In summary, this novel approach allows the rapid identification of epitopes contained in a given protein, direct determination of T-cell frequencies, and investigation of the T-cell clonality in the CD4 and CD8 T-cell subsets from as little as 2 times 20 ml of blood. Long-term follow-up of patients at risk for HCMV reactivation and disease may thus allow a more detailed insight into the complexity of the T-cell response to HCMV and may thus lead to improved diagnosis, prophylaxis and therapy.