Abstract not available

<p>In this thesis we examine the computational complexity of determining the satisfaction of various Mal'cev conditions. First we present a novel classification of linear idempotent Mal'cev conditions based on the form of the equations with which they are represented. Using this classification we present a class of conditions which can be detected in polynomial time when examining idempotent algebras. Next we generalize an existing result of Freese and Valeriote by presenting another class of conditions whose satisfaction is exponential time hard to detect in the general case, and en route we prove that it is equally hard to detect local constant terms. The final new contribution is an extension of a recent result of Maróti to a subclass class of weak Mal'cev conditions, proving that their detection is decidable and providing a rough upperbound for the complexity of the provided algorithm for said detection. We close the thesis by reviewing the current state of knowledge with respect to determining satisfaction of linear idempotent Mal'cev conditions.</p> / Doctor of Philosophy (PhD)

This dissertation deals with the classification of varieties according to their Mal'cev properties. In general the so called Mal'cev-type theorems illustrate an interplay between first order properties of a given class of algebras and the lattice properties of the congruence lattices of algebras of the considered class. CHAPTER 1. A survey of some notational conventions, relevant definitions and auxiliary results is presented. Several examples of less frequently used algebras are given together with the important properties of some of them. The term algebra T(X) and useful results concerning 'term' operations are established. A K-reflection is defined and a connection between a K-reflection of an algebra and whether a class K satisfies an identity of the algebra is established. CHAPTER 2. The Mal'cev-type theorems are presented in complete detail for varieties which are congruence permutable, congruence distributive, arithmetical, congruence modular and congruence regular. Several examples of varieties which exhibit these properties are presented together with the necessary verifications. CHAPTER 3. A general scheme of algorithmic character for some Mal'cev conditions is presented. R. Wille (1970) and A. F. Pixley (1972) provided algorithms for the classification of varieties which exhibit strong Mal'cev properties. This chapter is largely devoted to a modification of the Wille-Pixley schemes. It must be noted that this modification is quite different from all such published schemes. The results are the same as in Wille's scheme but slightly less general than in Pixley's. The text presented here, however is much simpler. As an example, the scheme is used to confirm Mal'cev's original theorem on congruence permutable varieties. Finally, the so-called Chinese var£ety is defined and Mal'cev conditions are established for such a variety of algebras . CHAPTER 4. A comprehensive survey of literature concerning Mal'cev conditions is given in this chapter. / Thesis (M.Sc.)-University of Natal, Durban, 1991.

The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NP-complete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech- niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3-conservative relational structures with only unary and binary relations either define NP-complete CSP, or CSP for them can be solved by the local consistency algorithm. 1

<p> A finiteness criterion is given for finitely generated positively ordered semigroups and this is used to show that various semigroups of operators in universal algebra are finite.</p> / Thesis / Master of Science (MSc)

String diagrams turn algebraic equations into topological moves that have recurring shapes, involving the sliding of one diagram past another. We individuate, at the root of this fact, the dual nature of polygraphs as presentations of higher algebraic theories, and as combinatorial descriptions of "directed spaces". Operations of polygraphs modelled on operations of topological spaces are used as the foundation of a compositional universal algebra, where sliding moves arise from tensor products of polygraphs. We reconstruct several higher algebraic theories in this framework. In this regard, the standard formalism of polygraphs has some technical problems. We propose a notion of regular polygraph, barring cell boundaries that are not homeomorphic to a disk of the appropriate dimension. We define a category of non-degenerate shapes, and show how to calculate their tensor products. Then, we introduce a notion of weak unit to recover weakly degenerate boundaries in low dimensions, and prove that the existence of weak units is equivalent to a representability property. We then turn to applications of diagrammatic algebra to quantum theory. We re-evaluate the category of Hilbert spaces from the perspective of categorical universal algebra, which leads to a bicategorical refinement. Then, we focus on the axiomatics of fragments of quantum theory, and present the ZW calculus, the first complete diagrammatic axiomatisation of the theory of qubits. The ZW calculus has several advantages over ZX calculi, including a computationally meaningful normal form, and a fragment whose diagrams can be read as setups of fermionic oscillators. Moreover, its generators reflect an operational classification of entangled states of 3 qubits. We conclude with generalisations of the ZW calculus to higher-dimensional systems, including the definition of a universal set of generators in each dimension.

Vollständig reguläre Halbgruppen weisen eine stark regelmäßige Struktur auf, die verschiedenste Zerlegungsmöglichkeiten gestatten. Ziel dieser Dissertation ist es, diese strukturelle Regelmäßigkeit auf Halbringe zu übertragen und die gewonnenen Algebren zu untersuchen. Mehrere Charakterisierungen werden herausgearbeitet, aufgrund derer es sich herausstellt, dass die Klasse aller vollständig regulären Halbringe eine Varietät bilden, deren Untervarietäten in der Folge untersucht werden. Zentrale Bedeutung haben dabei vollständig einfache Halbringe, deren Analyse einen der Schwerpunkte der Arbeit darstellt. Es zeigt sich, dass diese Bausteine vollständig regulärer Halbringe untereinander eine feste Struktur besitzen, selber aber auch als Zusammensetzung von isomorphen Halbringen aufgefasst werden können. Außerdem werden orthodoxe Halbringe, also Halbringe, deren idempotente Elemente einen Unterhalbring bilden, betrachtet. Zunächst wird dabei wieder auf mehrere Teilklassen eingegangen, bevor abschließend für beliebige vollständig reguläre Halbringe eine Beschreibung der kleinsten Kongruenz angegeben wird, deren Faktorhalbring orthodox ist.

Thesis (Ph. D. in Mathematics)--Vanderbilt University, 2003. / Title from PDF title screen. Includes bibliographical references and index.

Chapter 0 In this introductory chapter, certain notational and terminological conventions are established and a summary given of background results that are needed in subsequent chapters. Chapter 1 In this chapter, the notion of a "weak conguence formula" [Tay72], [BB75] is introduced and used to characterize both subdirectly irreducible algebras and essential extensions. Special attention is paid to the role they play in varieties with definable principal congruences. The chapter focuses on residually small varieties; several of its results take their motivation from the so-called "Quackenbush Problem" and the "RS Conjecture". One of the main results presented gives nine equivalent characterizations of a residually small variety; it is largely due to W. Taylor. It is followed by several illustrative examples of residually small varieties. The connections between residual smallness and several other (mostly categorical) properties are also considered, e.g., absolute retracts, injectivity, congruence extensibility, transferability of injections and the existence of injective hulls. A result of Taylor that establishes a bound on the size of an injective hull is included. Chapter 2 Beginning with a proof of A. Day's Mal'cev-style characterization of congruence modular varieties [Day69] (incorporating H.-P. Gumm's "Shifting Lemma"), this chapter is a self-contained development of commutator theory in such varieties. We adopt the purely algebraic approach of R. Freese and R. McKenzie [FM87] but show that, in modular varieties, their notion of the commutator [α,β] of two congruences α and β of an algebra coincides with that introduced earlier by J. Hagemann and C. Herrmann [HH79] as well as with the geometric approach proposed by Gumm [Gum80a],[Gum83]. Basic properties of the commutator are established, such as that it behaves very well with respect to homomorphisms and sufficiently well in products and subalgebras. Various characterizations of the condition "(x, y) Є [α,β]” are proved. These results will be applied in the following chapters. We show how the theory manifests itself in groups (where it gives the familiar group theoretic commutator), rings, modules and congruence distributive varieties. Chapter 3 We define Abelian congruences, and Abelian and affine algebras. Abelian algebras are algebras A in which [A2, A2] = idA (where A2 and idA are the greatest and least congruences of A). We show that an affine algebra is polynomially equivalent to a module over a ring (and is Abelian). We give a proof that an Abelian algebra in a modular variety is affine; this is Herrmann's Funda- mental Theorem of Abelian Algebras [Her79]. Herrmann and Gumm [Gum78], [Gum80a] established that any modular variety has a so-called ternary "difference term" (a key ingredient of the Fundamental Theorem's proof). We derive some properties of such a term, the most significant being that its existence characterizes modular varieties. Chapter 4 An important result in this chapter (which is due to several authors) is the description of subdirectly irreducible algebras in a congruence modular variety. In the case of congruence distributive varieties, this theorem specializes to Jόnsson's Theorem. We consider some properties of a commutator identity (Cl) which is a necessary condition for a modular variety to be residually small. In the main result of the chapter we see that for a finite algebra A in a modular variety, the variety V(A) is residually small if and only if the subalgebras of A satisfy (Cl). This theorem of Freese and McKenzie also proves that a finitely generated congruence modular residually small variety has a finite residual bound, and it describes such a bound. Thus, within modular varieties, it proves the RS Conjecture. Conclusion The conclusion is a brief survey of further important results about residually small varieties, and includes mention of the recently disproved (general) RS Conjecture. / Thesis (M.Sc.)-University of Natal, Durban, 2000.

Thesis (Ph.D.)--University of Cincinnati, 2008. / Committee/Advisors: David Herron PhD (Committee Chair), David Minda PhD (Committee Member), Nageswari Shanmugalingam PhD (Committee Member). Includes bibliographical references and abstract.