Universal Algebra and Logic
Spring 2009 Seminars
| Time: Tuesday, April 28. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Constantine Tsinakis Title: Interpolation and Amalgamation in Ordered Algebras III |
|
|
| Time: Tuesday, April 21. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Constantine Tsinakis Title: Interpolation and Amalgamation in Ordered Algebras II |
|
|
| Time: Tuesday, April 14. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Constantine Tsinakis Title: Interpolation and Amalgamation in Ordered Algebras Abstract: This talk, based on joint work with George Metcalfe and Franco Montagna, focuses on ordered algebras, that is, algebras with an underlying ordered structure. The interplay of algebra and logic takes center stage in our detailed study — in a universal algebraic setting — of the properties of amalgamation, interpolation and congruence extension. Specializing to varieties of residuated lattices, we present general techniques for establishing the amalgamation property for varieties of residuated lattices that are generated by their totally ordered members. |
|
|
| Time: Tuesday, April 7. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Ralph McKenzie Title: The complexity of constraint satisfaction problems: dichotomy holds for finite smooth graphs (a result of Barto, Niven and Kozik) III |
|
|
| Time: Tuesday, March 31. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Ralph McKenzie Title: The complexity of constraint satisfaction problems: dichotomy holds for finite smooth graphs (a result of Barto, Niven and Kozik) II |
|
|
| Time: Tuesday, March 24. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Ralph McKenzie Title: The complexity of constraint satisfaction problems: dichotomy holds for finite smooth graphs (a result of Barto, Niven and Kozik) Abstract: The subject is finite graphs and the constraint satisfaction problem. All graphs $\m g$ will be directed. $\mbox{CSP}(\m g)$ is the problem, to input any finite graph $\m s$, and output the correct answer to the question “is $\mbox{hom}(\m s,\m g)\neq \emptyset$?” (One seeks a mapping from $S$ to $G$ satisfying the constraints imposed by the edge-relations of the two graphs.) A graph is a {\it core} if all of its endomorphisms are automorphisms. A core of $\m g$ is a subgraph $\m c$ that is a retract of $\m g$, and is a core. Every finite graph has a core, unique up to isomorphism. A graph is {\it smooth} if each of its vertices has non-zero in-degree and non-zero out-degree. Our goal is to prove the “smooth-graph theorem” of L. Barto, T. Niven and M. Kozik—for every smooth finite graph $\m g$, $\mbox{CSP}(\m g)$ is solvable by a deterministic polynomial time algorithm if the core of $\m g$ is a disjoint union of circles, and otherwise $\mbox{CSP}(\m g)$ is an NP-complete computational problem. From known algebraic results, this reduces to proving, for any smooth finite graph $\m g$, that the core of $\m g$ is a disjoint union of circles provided $\m g$ admits a graph-homomorphism $\varphi: \m g^n\rightarrow \m g$ for some $n>1$ such that for all $x,y\in G$, $\varphi(x,x,\ldots,x)=x$ and $$ \varphi(y,x,\ldots,x)=\varphi(x,y,x,\ldots,x)=\cdots =\varphi(x,x,\ldots,x,y)\,. $$ Such a mapping $G^n\rightarrow G$ is called a {\it weak nu} operation on $G$, and if it is a homomorphism $\m g^n\rightarrow \m g$ then it is termed a {\it weak nu polymorphism} of $\m g$. The proof is dense and complex, and once begun, will occupy several weeks of seminar |
|
|
| Time: Tuesday, March 17. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Petar Markovic Title: Type 5 simple algebras in varieties omitting type 1 |
|
|
| Time: Thursday, March 12. (SC 1312, 2:30 – 3:20 p.m.) Speaker: George McNulty, University of South Carolina Title: The equational complexity of Lyndon’s algebra Abstract: With every algebra A of finite signature we associate an equational complexity function $\beta(n)$ which, loosely speaking measures how much of the equational theory of A must be examined to determine if an algebra with fewer than n elements belongs to the variety generated by A. For Lyndon’s algebra we show that $n – 4 < \beta(n) \le 2n + 1$ for $3 < n$.This is also joint work with Marcel Jackson. |
|
|
| Time: Wednesday, March 11. (SC 1312, 4:10 – 5:10 p.m.) Speaker: George McNulty, University of South Carolina Title: Lyndon’s algebra is inherently nonfinitely based relative to the class of automatic algebras Abstract: In 1954 Roger Lyndon published the earliest example of a finite algebra with a nonfinitely axiomatizable equational theory. His proof, syntactical in nature, runs to a page and a half. In this talk I will present a much longer proof. This proof proceeds by constructing algebras. There is a natural way to convert any finite automaton into an algebra. Lyndon’s algebra can be obtained in this way. It turns out that Lyndon’s algebra is inherently nonfinitely based relative to the variety generated by the class of automatic algebras. So we will also explain this relative notion of nonfinite axiomatizability. This is joint work with Marcel Jackson. |
|
|
| Time: Tuesday, February 24. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Francesco Paoli, University of Cagliari, Italy, & Vanderbilt University Title: Algebras from quantum computation Abstract: I will survey the main results obtained by our research group on quasi-MV algebras and quasi-MV algebras with square root of the inverse, (expansions of) generalisations of MV algebras arising as an abstraction from the algebra of density operators on the 2-dimensional complex Hilbert space endowed with special quantum gates. I will focus especially on results that might be of interest for an audience of universal algebraists, namely: i) a description of the lattices of subvarieties for both varieties; ii) a version of Jonsson’s lemma; iii) the axiomatisation of the subvariety generated by an algebra which has an intrinsic motivational interest. |
|
|
| Time: Tuesday, February 17. (SC 1308, 4:10 – 5:10 p.m.) Speaker: Petar Markovic Title: Omitting type 1 in locally finite varieties Abstract: Having a type 1 in the variety generated by a finite idempotent algebra implies that any CSP problem with the template consisting of relations which are invariant under operations of A (i. e. subalgebras of powers of A) is NP-complete. The algebraic strengthening of the CSP dichotomy conjecture (so-called Algebraic Dichotomy Conjecture) claims that if the variety generated by A omits type 1 then any CSP problem with the template consisting of relations which are invariant under operations of A is tractable. In order to develop tools for attacking this conjecture, it is necessary to examine in detail what it means for a finitely generated, or even locally finite, variety to omit type 1. This is the most general nontrivial idempotent Malcev property a locally finite variety can have. I will give an overview of all known conditions in the historical order they were discovered. The highlight should be the two recent (Fall 2008) results, one (by Siggers, improved a little by Kearnes, McKenzie and ~) showing that this is a strong Malcev property of locally finite varieties, and the other one which works only in the finitely generated case (by Barto and Kozik) which gives a Malcev property equivalent to having fixed points for automorphisms of large prime order throughout the variety. Though the abstract may lead the audience to conclude that I will give a highly technical talk, I will try to keep it pretty basic and give at least intuitive fill-ins for definitions for concepts too advanced to define properly to a non-expert audience. The idea is to give a big picture of the current knowledge of this topic and by extension, the tools currently available for attack at the Algebraic Dichotomy Conjecture. |
|
|
| Time: Tuesday, January 27. (SC 1308, 4:10 – 5:10 p.m.) Speaker: George Metcalfe Title: Modal Fuzzy Logics: A Proof-Theoretic Perspective Abstract: The aim of this talk is to give a brief introduction to some important proof systems for modal logics and fuzzy logics and to show how these two approaches can be combined to give a proof system for a particular modal fuzzy logic. This proof system will then be used to obtain some theoretical results for the logic. The only requirement for understanding (most of) the talk is some familiarity with propositional classical logic or Boolean algebras. |
|
|
| Time: Tuesday, January 20. (SC 1308, 4:10 – 5:10 p.m.) Speaker: George Metcalfe Title: Routes to Non-Classical Logics: Modal Logics, Fuzzy Logics, and Modal Fuzzy Logics Abstract: Classical Logic is based on two key assumptions: (1) bivalence, that every sentence is either true or false, and (2) truth functionality, that the truth value of a complex formula is a function of the truth values of its constituent parts. Dropping either one of these assumptions leads to various families of non-classical logics. In particular, dropping bivalence and allowing truth values to range over the real unit interval [0,1] leads to “fuzzy logics” suitable for modelling vagueness in sentences such as “John is tall” or “The water is hot”. Dropping truth-functionality allows treatments of modal notions such as necessity, knowledge, provability, and spatio-temporal relationships, and leads to the much studied class of modal logics. The intention of this talk is to give an introduction to the basic ideas of both these families of logics, and then to describe some of my own recent work on combining the two approaches to obtain modal fuzzy logics. The only requirement for understanding the talk is some familiarity with propositional Classical Logic or Boolean algebras. |
©2024 Vanderbilt University ·
Site Development: University Web Communications