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
meetings.
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.
Time: Tuesday, December 9. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Justin Brody
Title: On Rational Limits of Shelah-Spencer Graphs
Abstract: For $\alpha$ irrational in $(0,1)$, the random graph $G(n, n^{- \alpha})$ is a finite probability space whose events are order $n$-graphs which occur with probability determined by
declaring that any potential edge will occur with probability
$n^{-\alpha}$. Work of Shelah, Spencer, and Baldwin has shown that the limiting behavior of these graphs as $n \to \infty$ is very tame. In particular there is a unique countable graph $G_\alpha$ which functions as a certain limit of these graphs. We will examine ultraproducts $\Prod_U G_{\alpha_n}$ for $\{\alpha_n \}$ an irrational sequence in $(0,1)$ converging to a rational.
Time: Tuesday, December 2. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras IV
Time: Tuesday, November 18. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras III
Time: Tuesday, November 11. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras II
Time: Tuesday, November 4. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras
Abstract: Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general (it includes graph three-coloring), but certain restrictions on the form of constraints can ensure tractability. Feder and Vardi (1998) conjectured that every “specific” instance of the CSP (such as graph three-coloring) is either tractable or NP-complete. Bulyatov and Jeavons (2002) showed that to every specific instance of CSP is correlated a finite algebra and that relative complexity of two CSP problems is directly tied to structural relations between the correlated algebras. They proposed general algebraic criteria for an instance of CSP to be tractable, or NP-complete. Thus they created an algebraic version of the dichotomy conjecture of Feder and Vardi, which is currently the focus of a lot of research.
Remarkable progress has been made on the dichotomy conjecture during the past two years. Using a combination of universal-algebraic and graph-theoretic ideas, a team of young central european mathematicians has shown that for a finite algebra A for which no non-trivial Abelian congruences occur in the variety it generates, all CSP problems involving admissible relations over A are tractable. My talks will discuss in detail an easier proof of a result the team proved two months ago, on the way to the mentioned result: if a relational structure R has Jonsson terms among its polymorphisms, then the (2p, 3p)-consistency algorithm solves CSP(R) in polynomial time.
Time: Tuesday, October 28. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Constantine Tsinakis
Title: Universal Algebra for the Working Mathematician II.
Time: Tuesday, October 14. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Constantine Tsinakis
Title: Universal Algebra for the Working Mathematician.
Abstract: The title of the talk captures its aims. My intention is to provide an account of those fundamental results in the area that every well-educated research mathematician would find useful in his/ her research. One of the aims of universal algebra is to study features common to many familiar algebraic systems, such as groups, rings, lattices, etc. Such a study places a number of algebraic notions in their proper setting, reveals connections of seemingly unrelated concepts, and uses the higher level of abstraction to apply these results to entirely new situations. A central theme in this area is that of a variety or an equational class.
Time: Tuesday, October 7. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: An Idiot's Guide to Complexity II.
Time: Tuesday, September 30. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: An Idiot's Guide to Complexity I.
Abstract:I will attempt to give the basic concepts, ideas and results of the theory of computational complexity. The lecture is geared towards first-year graduate students and people who may have heard these notions before but never in a systematic way.
Time: Tuesday, September 23. (SC 1308, 4:30 - 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University
Title: Proof Theory and Algebra I.
Abstract: Classes of algebraic structures, such as groups, lattices, Boolean algebras etc. are often presented using a list of identities (equations) that specify when an algebra belongs to the class. However, this presentation does not help much in testing whether a particular identity holds for all members of the class. In this talk, I will introduce alternative algorithmic or "proof-theoretic" presentations of classes of algebras, and explain some of the main results, applications, and challenges in the field.
Time: Tuesday, September 16. (SC 1308, 4:30 - 5:50 p.m.)
Speaker: Matthew Nickodemus, Vanderbilt University
Title: The Stone Duality Theorem.
Abstract: In 1936, Marshall Stone proved that every Boolean algebra is isomorphic to the algebra of all clopen subsets of some totally disconnected compact space. In this talk, I will prove Stone's Theorem. My talk will be aimed at first year graduate students, and advanced undergraduates
Time: Tuesday, September 9. (SC 1308, 4:10 - 5:30 p.m.)
Title: Organizational Meeting.
Time: Tuesday, April 22. (SC 1432, 4:10 - 5:30 p.m.)
Speaker: Carmela Sica, University of Salerno
Title: Centralizers in locally finite groups
Abstract: Let G be a locally finite group admitting an automorphism f of finite order such that the centralizer C_G(f) satisfies certain finiteness conditions. What impact does this have on the structure of the group G? Starting from some nown results, it will be shown that if G is locally finite and admits a four-group of automorphisms without non-trivial fixed points, then the derived subgroup G' is a product of normal nilpotent subgroups. This is joint work with Pavel Shumyatsky.
Time: Tuesday, April 8. (SC 1432, 4:10 - 5:30 p.m.)
Speaker: Matthew Gould, Vanderbilt University
Title: Interassociativity
Abstract: Semigroups (S, #) and (S, *) are said to interassociate with each other if the algebra (S, # , *) satisfies the equations (x#y)*z = x#(y*z) and (x*y)#z = x*(y#z). Old and new results on interassociativity and related topics will be reviewed.
Time: Friday, March 28. (SC 1310, 1:10 - 2:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Time: Tuesday, March 11. (SC 1432, 4:10 - 5:30 p.m.)
Speaker: Rostislav Horcik, Czech Academy of Sciences
Title: Applications of non-formally-integral totally ordered monoids in non-classical logics
Speaker: Petr Cintula, Czech Academy of Sciences
Title: Hierarchies of implications and disjunctions in non-classical logics
Time: Tuesday, February 26. (SC 1432, 4:10 - 5:30 p.m.)
Speaker: Yuri Bahturin
Title: Functional Identities and Graded Algebras
Abstract: Functional identities are the identical relations for arbitrary functions on algebras. This is a comparatively new piece of techniques which was recently successfully used in the study of Lie, Jordan and other types of maps on associative algebras to prove famous Herstein conjectures. This is summarized in a recent monograph "Functional Identities" by M. Bresar, M. Chebotar and W. Martindale. It was recently discovered that using elementary techniques of Hopf algebras these results can be applied to the study of graded algebras.
Time: Tuesday, February 12. (SC 1432, 4:10 - 5:30 p.m.)
Speaker: Ciro Russo, Vanderbilt University
Title: Propositional deductive systems: hidden interpretability, fragments and equivalence.
Abstract: The interpretability of one logic into another is a very common issue in Mathematical Logic but, as far as we know, a precise and general definition of the concept of "interpretation" is still lacking, the meaning of this word usually relying on a logician's intuition. We propose a general and purely syntactic definition of interpretability for the case of propositional deductive systems. Then we generalize this definition, together with the notions of equivalence of deductive systems and a fragment of a logic, to corresponding "hidden" notions. Such generalizations are amenable to an algebraic characterization that, under additional hypotheses, yield results for the corresponding non-hidden notions.
Time: Monday, February 4. (SC 1310, 1:10 - 2:30 p.m.)
Speaker: Olga Sapir, Vanderbilt University
Title: Finitely generated permutative varieties (Part II).
Time: Monday, January 28. (SC 1310, 1:10 - 2:30 p.m.)
Speaker: Olga Sapir, Vanderbilt University
Title: Finitely generated permutative varieties (Part I).
Abstract: We show that there exists an algorithm which decides whether a finite set of identities containing a permutation identity defines a variety generated by a finite semigroup or not.
Time: Tuesday, November 27. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University
Title: Interpolation and amalgamation for abelian l-groups and MV-algebras
Abstract: Algebra and Logic are closely related and often mutually beneficial companions. In this talk, I will show how the logical property of interpolation can be used as a stepping stone to the algebraic property of amalgamation. In particular, I will give a simple proof of the deductive interpolation property for abelian l-groups, that provides as nice by-products, not just amalgamation, but also generation of the variety by the integers Z, and decidability. This proof can also be extended to the variety of MV-algebras, the algebraic semantics for Lukasiewicz logic.
Time: Tuesday, November 13. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: Constantine Tsinakis, Vanderbilt University
Title: Residuated structures: Their Algebra and Logic (Part 2)
Abstract: The focus of this talk is residuated lattices and their logical counterparts, the so called substructural logics. The talk has the following objectives: (1) Show how the algebraic theory of residuated lattices can produce powerful tools for the comparative study of substructural logics. (2) Demonstrate that the bridge algebraic logic builds is beneficial to both algebra and logic. I illustrate this fact with a detailed discussion of the connection between the algebraic property of amalgamation and the logical property of interpolation.
Time: Tuesday, November 6. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: Constantine Tsinakis, Vanderbilt University
Title: Residuated structures: Their Algebra and Logic
Abstract: The focus of this talk is residuated lattices and their logical counterparts, the so called substructural logics. The talk has the following objectives: (1) Show how the algebraic theory of residuated lattices can produce powerful tools for the comparative study of substructural logics. (2) Demonstrate that the bridge algebraic logic builds is beneficial to both algebra and logic. I illustrate this fact with a detailed discussion of the connection between the algebraic property of amalgamation and the logical property of interpolation.
Time: Tuesday, October 30. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University
Title: Definability in substructure orderings (Part 2)
Time: Tuesday, October 9. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University
Title: Definability in substructure orderings
Abstract: This is joint work with Jaroslav Jezek. Let P be the ordered set of isomorphism types of finite ordered sets, ordered by embeddability. We show that every isomorphism-invariant relation between posets that is first-order definable in the category of finite posets (where the morphisms are the monotone maps), is first-order definable up to duality in P. This implies, but is stronger than, the conclusion that every self-dual class of finite posets axiomatized by a second-order sentence in the language of posets is first-order definable in P. In particular, for every finite poset A, the set consisting of the isomorphism type of A and the isomorphism type of the dual of A, is first-order definable in the ordered set P. We prove analogous but slightly weaker results for the ordered sets consisting of isomorphism types of finite lattices (or semilattices, or distributive lattices, respectively) ordered by embeddability. In all cases, the individual isomorphism types are definable up to duality, and duality is the only automorphism of the ordered set of types.
Time: Tuesday, October 2. (SC 1308, 4:10 - 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: Bounded width CSP: An overview
Abstract: We will present one of the most general algorithms for solving the Constraint Satisfaction Problem in polynomial time, give a boundary on the cases where it may be attempted and prove it works in some of these cases. The attendees will be assumed to have heard the previous lecture in this seminar, though some definitions will be repeated.
Time: Tuesday, September 18. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: Complexity of the constraint satisfaction problem, an universal-algebraic approach
Abstract: This lecture will review the currect state of knowledge on a major problem of computational complexity: whether any (restricted) constraint satisfaction problem can have only two complexities, polynomial and NP-complete. We will discuss an approach using the techniques of universal algebra, which has proved most successful so far. We will review the latest known results, including the one by the speaker (in collaboration with C. Carvalho and V. Dalmau) which was proved in August 2007.
Time: Tuesday, September 11. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Franco Montagna, University of Siena, Italy
Title: Representations of GBL-algebras
Abstract: My objective is to develop different types of representations for BL and GBL-algebras. The presentation will be self-contained and include definitions and detailed discussion of the main mathematical structures arising in this talk. These representations will be used to establish various decidability results.
Time: Tuesday, April 24. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ciro Russo, University of Salerno, Italy
Title: An order-theoretical approach to image processing
Abstract: We show that an order-theoretical and algebraic approach to some techniques of image compression - that make use of the theory of fuzzy relation equations - gives rise to interesting results in the theory of modules over residuated lattices. Such results have, in their turn, effects on the applications. Moreover, this approach yields new methods and techniques, and strongly motivates a deep investigation of the mathematical concepts involved.
Time: Tuesday, April 17. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Jaroslav Jezek, Charles University, Czech Republic
Title: Definability for semilattices.
Abstract: We prove that the lattice of universal classes of semilattices has only the identical automorphism and its finitely generated and finitely axiomatizable elements are definable.
Time: Tuesday, April 10. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University
Title: Herbrand's Theorem and Skolemization by Approximation for First-Order Lukasiewicz Logic
Abstract: Herbrand's theorem and Skolemization are key results for first-order classical logic. In this talk I will explain how they transfer to the case of infinite-valued first-order Lukasiewicz logic. We will see that while the usual Herbrand theorem fails, an approximate Herbrand theorem can be proved and used to establish Skolemization.
Time: Tuesday, April 3. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Anton Klyachko, Moscow State University.
Title: Groupification of universal algebras
Abstract: We show that many universal algebras admit group structures such that all operations can be expressed via multiplication, inverse, and constants.
Time: Tuesday, March 20. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Yuri Bahturin, Memorial University, Canada.
Title: Large Lie algebras and Burnside type problems
Abstract: I will speak on the results of our joint work with Alexander Olshanskii. I will define restricted Lie algebras and show that some problems about Lie algebras in characteristic p>0 can be reduced to restricted Lie algebras. The advantage of restricted Lie algebras is that their properties are closer to groups. This allows us to use group theoretic approaches, in particular the approach of Olshanskii - Osin that allowed to construct new examples of Burnside type groups. We introduce and study large restricted Lie algebras, that is, algebras each of which contains a subalgebra of finite codimension that maps onto a nonabelian free restricted algebra. We describe a procedure that allows us to construct finitely generated restricted nil algebras that are direct limits of large algebras. This yields apparently new examples of finitely generated nil (=Engel) Lie algebras.
Time: Tuesday, February 20. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Gabor Kun, RWTH Aachen University, Germany.
Title: NP by forbidden lists
Abstract: We present three definitions of the class NP in terms of homomorphisms of colored digraphs: in terms of injective homomorphisms, full homomorphisms and colorings of pairs, respectively. We apply this to special syntactically defined subclasses of NP. The most of the applications of our viewpoint are about the relationship of the class of Constraint Satisfaction Problems (CSP) and Monotone Monadic SNP (MMSNP) defined by Feder and Vardi. Our setting streamlines the analysis of these languages. We give a characterization (with simple proof) of MMSNP languages which are actually CSP languages. We show that an MMSNP language of digraphs restricted to a bounded expansion class (a generalization of bounded degree and minor closed classes) is actually a CSP language.
Time: Tuesday, February 13. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University
Title: Avoidable distributive lattices and nicely structured ordered sets
Time: Tuesday, January 30. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Dan Guralnik, Vanderbilt University
Title: Reflections on memory, language, logic and non-positively curved cube complexes
Abstract: In this talk I will try to share with you some of my naive ideas about how one could try to bring our understanding of natural languages, cognitive models of memory, ideas from Ethology -- the study of animal behaviour -- and information theory under the umbrella of a formal mathematical theory describing the connections between the above. The talk will have two parts. In the first, I will introduce the mathematical tool -- the Sageev-Roller duality between partially-ordered sets with an involution (poc-sets) and cubical complexes of non-positive curvature (cubings, for short). In the second part, I will discuss the application.
Time: Tuesday, January 23. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Wieslaw Dziobiak, University of Puertro Rico, Mayaguez
Title: One More Proof of Willard's Finite Basis Theorem
Abstract: Willard's finite basis theorem states that the set of universally valid equations in a congruence meet semi-distributive and residually very finite variety of algebras of finite signature has a finite equational base (R. Willard, JSL 65 (2000), 187-200). The goal of the talk is to present a short proof of Willard's theorem. The crucial ingredient of the presented proof is a consequnce of a result that is contained in the paper by W. Dziobiak, M. Maroti, R. McKenzie, and A. Nurakunov, Fund. Math. (to appear). Other known new proofs of Willard's theorem are contained in the papers by K. Baker, G. McNulty, and Ju. Wang (AU 52 (2004), 289-302) and M. Maroti and R. McKenzie (SL 78 (2004), 393-320).
Time: Tuesday, February 6. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Jaroslav Jezek, Charles University, Czech Republic
Title: Avoidable posets, semilattices and lattices
Abstract: A finite structure A is said to be avoidable in a class of structures K if there exists an infinite set S of finite structures from K such that A belongs to S and no structure from S can be embedded into another structure from S. We will speak about avoidable and unavoidable posets, semilattices and lattices.
Time: Monday, December 11. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University
Title: Existence Theorems for Weakly Symmetric Operations, I
Time: Monday, December 4. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University
Title: Existence Theorems for Weakly Symmetric Operations, II
Time: Monday, November 13. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University
Title: Admissible Rules
Abstract: Investigation of logical systems usually concentrates on the derivability of theorems. However, it is also interesting to ``move up a level'' and to consider which rules are admissible for the system. That is, to investigate under which rules the set of theorems is closed. In Classical logic, admissible rules are also derivable; however, in Intuitionistic logic, and many other non-classical (e.g. modal and intermediate) logics this is no longer the case. In recent years, the most successful approach to characterizing admissible rules has been via bases: sets of admissible rules that when added to a logic allows all admissible rules of that logic to be derived. In joint work with Rosalie Iemhoff, we have given a general framework for defining "Gentzen-style" proof theory for admissibility; the idea being to give a uniform characterization of the admissible rules of a logic by generalizing proof calculi at the theorem level. Just as for derivability the basic objects are sequents of formulas rather than formulas, for admissibility, the basic objects of our systems are sequent rules rather than rules. We present analytic calculi in this framework for admissibility in Intuitionistic logic, and various modal and intermediate logics.
Time: Monday, November 6. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Wieslaw Dziobiak, University of Puertro Rico, Mayaguez
Title: Endomorphisms of Monadic Boolean Algebras
Abstract: A classical result about Boolean algebras -- independently proved by Magill, Maxson, and Schein -- states that non-trivial Boolean algebras are isomorphic whenever their endomorphism monoids are isomorphic. The main point of this talk is to show that the finite part of this classical result is true within monadic Boolean algebras. By contrast, there exists a proper class of non-isomorphic (necessarily) infinite monadic Boolean algebras the endomorphism monoid of each of which has only one element (namely, the identity map). [Joint work with M.E. Adams (SUNY)]
Time: Monday, October 30. (SC 1312, 4:10 - 5:30 p.m.)
Speaker:Jaroslav Jezek, Charles University, Czech Republic
Title:Definability for lattices of varieties
Abstract: The problems of definability in the lattice of all varieties of a given signature can be answered in the positive. These are older results. We are going to discuss their possible extension to the lattice of subvarieties of a given variety in some particular cases.
Time: Monday, October 23. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Constantine Tsinakis, Vanderbilt University
Title: Residuated lattices: An introduction for the working mathematician
Abstract: Residuated lattices -- and more generally, residuated structures, first appeared explicitly in the work of Krull, Ward and Dilworth as abstractions of ideal lattices of rings in the early 1930's. Their study, however, goes back to Hilbert's foundational studies of geometry, and Riesz's development of the theory of operators and their spaces. Dedekind's work restored unique factorization at the level of ideals, of what we nowadays call Dedekind domains, and had as its ultimate objective the proof of Fermat's last theorem, which became a reality only recently. Dedekind's research provided the seeds for the valuation theory of integral domains, abstract ideal theory and modern algebraic theory of residuated structures. An appealing feature of residuated structures is that they are now recognized as being connected with a host of interesting areas of mathematics, logic, proof theory, computer science and computer engineering. My aim is to present a self-contained introduction of the fundamental results of this research area. En route, I will discuss numerous results from classical mathematics.
Time: Monday, October 9. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Matthew Gould, Vanderbilt University
Title: The Structure of Bands
Abstract: A band is a semigroup that satisfies the equation xx = x. If a band is commutative it is called a semilattice. A band that satisfies xyz = xz is said to be rectangular. The structure of rectangular bands will be described, and bands in general will be described in terms of semilattices and rectangular bands. The general structure theory will be seen to take on a particularly nice form when applied to normal bands, i.e., bands satisfying xuvy = xvuy. If time permits, the structure theory will be used to establish a new result, due to the speaker and M.E. Adams, on retractions of bands.
Time: Monday, October 2. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Wieslaw Dziobiak, University of Puertro Rico, Mayaguez
Title: Quasi-equational Classes of Wajsberg Algebras.
Abstract: Wajsberg algebras are the algebraic models of Lukasiewicz infinite valued propositional logic. The aim of the talk is to present what is known and what is unknown about quasi-equational classes of Wajsberg algebras.
Time: Monday, September 25. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ethan Jackson, Institute for Software Integrated Systems, Department of Computer Engineering and Computer Science, Vanderbilt University.
Title: Towards a Formal Foundation for Domain Specific Modeling Languages.
Abstract: (A disclaimer: I will begin my presentation with an explanation of the terms used in the abstract that follows.) Embedded system design is inherently domain specific and typically model driven. As a result, design methodologies like OMG�s model driven architecture (MDA) and model integrated computing (MIC) evolved to support domain specific modeling languages (DSMLs). The success of the DSML approach has encouraged work on the heterogeneous composition of DSMLs, model transformations between DSMLs, approximations of formal properties within DSMLs, and reuse of DSML semantics. However, in the effort to produce a mature design approach that can handle both the structural and behavioral semantics of embedded system design, many foundational issues concerning DSMLs have been overlooked. In this presentation I will present a formal foundation for DSMLs and for their construction within metamodeling frameworks. This foundation allows one to algorithmically decide if two DSMLs or metamodels are equivalent, if model transformations preserve properties, and if metamodeling frameworks have meta-metamodels. These results are key to building correct embedded systems with DSMLs.
Time: Monday, September 18. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University.
Title: A Short Tutorial on Fuzzy Logics.
Abstract: Fuzzy logics can be characterized as "logics based on the real numbers". That is, logics where degrees of truth are real numbers and connectives are interpreted by functions on the reals. Such logics are usually designed with applications in mind as workhorses of the wider enterprise of Fuzzy Logic, which originated with the formalization of fuzzy sets by Lotfi Zadeh in the 1960s. Fuzzy logics provide the basis for logical systems dealing with vagueness; e.g. to formalize natural language predicates such as "tall" or "fast". Just like Classical Logic, fuzzy logics can be axiomatized and investigated using methods from Universal Algebra and Proof Theory. The purpose of this short tutorial is to explain how fuzzy logics may be viewed as the result of certain "design choices" (about the truth values and the behaviour of connectives) and to describe some interesting mathematical questions arising in this context.
Time: Monday, September 11. (SC 1312, 4:10 - 5:30 p.m.)
Speaker: Ralph McKenzie, Vanderbilt University.
Title: Complexity of Some Algorithmic Problems for Finite Algebras.
Abstract: In this talk I discuss (and maybe prove) some results from the paper M. Jackson, R. McKenzie, Graph colourability in finite semigroups which appears in the International Journal of Algebra and Computation, volume 16 (2006), pp. 119-140. In the paper, we were principally concerned with the finite membership problem for the variety generated by a finite algebra A (and mainly in the case that A is a semigroup). This is the problem to determine, given any finite algebra B of the same signature as A, whether B belongs to that variety, i.e., belongs to the class HSP(A). Actually, we sought to discover lower bounds on the complexity of any algorithm which, on any input B (or on input of some string of digits that codes a description of B in a standard manner), will output the correct answer to the question "Is B 2 HSP(A)?" This problem is known to be inherently computationally difficult, for certain finite algebras A. A natural algorithm exists for these problems, but it appears that in the worst case, it may have a high degree of complexity, requiring a very long run-time. The best known calculation for the run-time of this algorithm shows only that it is no worse than doubly exponential in the length of the input. We sought to prove or disprove that the least upper bound for the complexity of the most efficient algorithm to solve the finite membership problem for HSP(S), where S ranges over all finite semigroups, is in fact doubly exponential time. As a first approximation, we obtained the central result of this paper, which is the presentation of a 55-element semigroups S such that the finite membership problem for the variety generated by S is NP-hard. We built S by interpreting finite graphs into finite semigroups, in a certain fashion. To show that the problem is NP-hard, we exhibited a construction which, given any finite simple graph G, produces in polynomial time a finite semigroup S(G) such that S(G) 2 HSP(S) iff G is three-colourable. Since threecolourability of finite simple graphs is known to be an NP-complete problem, then any problem in the class NP (non-deterministic, polynomial time computable) admits a (deterministic) polynomial time interpretation into the finite membership problem for HSP(S). We also showed that a number of other natural membership problems for classes associated with finite semigroups are computationally difficult. Some of these results will be described. I will present our construction of S and S(G), and outline as completely as time allows, our proof for the above-stated results about them.
Time: Tuesday, April 11. (SC 1403, 4:00 p.m.)
Speaker: Eric Zenk
Title: Presenting Regular frames
Abstract: Frames (complete lattices where finite meets distribute over joins) give an interesting perspective on topology. Regular frames have the feature that each congruence is determined by the congruence class of 1. Using this well known fact, I develop a convenient scheme for presenting regular frames. These presentations allow reasonably easy calculation of colimits of regular frames.
Time: Tuesday, March 21. (SC 1403, 4:00 p.m.)
Speaker: Ralph McKenzie
Title: Varieties with Few Subalgebras of Powers
Abstract:
Time: Tuesday, March 14. (SC 1403, 4:00 p.m.)
Speaker: Ralph McKenzie
Title: Varieties with Few Subalgebras of Powers
Abstract:
Time: Tuesday, March 7. (SC 1403, 4:00 p.m.)
Speaker: Ralph McKenzie
Title: Varieties with Few Subalgebras of Powers
Abstract:
Time: Tuesday, February 28. (SC 1403, 4:00 p.m.)
Speaker: Ralph McKenzie
Title: Varieties with Few Subalgebras of Powers
Abstract:
Time: Thursday, March 24. (SC 1403, 2:00 p.m.)
Speaker: Nick Galatos
Title: Equivalence of logical consequence operations: an order theoretic perspective (continued).
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, March 22. (SC 1403, 2:00 p.m.)
Speaker: Eric Zenk
Title: Introduction to E-reflective subcategories.
Abstract: A quasivariety is a class of algebras closed under taking products embedded subalgebras and ultraproducts, or equivalently, a class of algebras defined by a set of quasiequations. The notion of a product-closed class makes sense in practically every category one examines. However, both the notion of quasi-equation and embedded substructure are more difficult to generalize. The talk will describe language for dealing with situations in which more than one notion of embedded subobject make sense. Given such a notion of embedding, an E-reflective subcategory is precisely a class closed under products and embeddings. (It seems there is no suitable generalization of quasi-equation.) Examples in topology and the context of partially ordered sets will be given.
Time: Thursday, March 17. (SC 1403, 2:00 p.m.)
Speaker: Nick Galatos
Title: Equivalence of logical consequence operations: an order theoretic perspective (continued).
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, March 15. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Abstract: Ralph McKenzie will continue a series of lectures on Complexity questions for finite algebras.
Time: Thursday, March 10. (SC 1403, 2:00 p.m.) No meetings. Spring Break.
Time: Tuesday, March 08. (SC 1403, 2:00 p.m.) No meetings. Spring Break.
Time: Thursday, March 03. (SC 1403, 2:00 p.m.)
Speaker: Nick Galatos
Title: Equivalence of logical consequence operations: an order theoretic perspective (continued).
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, March 01. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Abstract: Ralph McKenzie will continue a series of lectures on Complexity questions for finite algebras.
Time: Thursday, February 24. (SC 1403, 2:00 p.m.)
Speaker: Nick Galatos
Title: Equivalence of logical consequence operations: an order theoretic perspective, V.
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, February 22. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Thursday, February 17. (SC 1403, 2:00 p.m.)
Speaker: Nick Galatos
Title: Equivalence of logical consequence operations: an order theoretic perspective, IV.
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, February 15. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Thursday, February 10. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Tuesday, February 8. (SC 1403, 2:00 p.m.)
Speaker: Constantine Tsinakis
Title: Equivalence of logical consequence operations: an order theoretic perspective, II.
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Thursday, February 3. (SC 1403, 2:00 p.m.)
Speaker: Constantine Tsinakis
Title: Equivalence of logical consequence operations: an order theoretic perspective, II.
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, February 1. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Thursday, January 27. (SC 1403, 2:00 p.m.)
Speaker: Constantine Tsinakis
Title: Equivalence of logical consequence operations: an order theoretic perspective, I.
Abstract: The aim of this series of talks is to propose and study an order theoretic and categorical framework for the study of the general notion of an abstract logical equivalence between two logical consequence relations. Our development leads naturally to the discussion of translations between two such operations, and pays particular attention to the abstraction of the concept of a structural transformer.
Time: Tuesday, January 25. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Tuesday, January 18. (SC 1403, 2:00 p.m.)
Speaker: Ralph McKenzie
Title: Complexity questions for finite algebras.
Time: Thursday, December 9. (SC 1404, 2:30 p.m.)
Speaker: Ralph McKenzie
Title: Does there exist a non-trivial meet-semi-distributive algebraic lattice that has no non-trivial meet-prime element? (Part II)
Time: Tuesday, December 7. (SC 1403, 2:10 p.m.)
Speaker: Ralph McKenzie
Title: Does there exist a non-trivial meet-semi-distributive algebraic lattice that has no non-trivial meet-prime element?
Time: Thursday, December 2. (SC 1404, 2:30 p.m.)
Speaker: Ralph McKenzie
Title: Some special examples of algebraic lattices.
Time: Tuesday, November 30. (SC 1403, 2:10 p.m.)
Speaker: David Stanovsky
Title: Commutative idempotent residuated lattices.
Abstract: We will show a couple of interesting properties of the variety of residuated lattices with commutative and idempotent multiplication. In particular, they satisfy no non-trivial lattice equation, they contain a non-finitely based subvariety, they contain two minimal subvarieties and I can describe those with totally ordered lattice reduct.
Time: Thursday, November 18. (SC 1404, 2:30 p.m.)
Speaker: David Stanovsky
Title: Idempotent left distributive left quasigroups, Part II.
Abstract: We continue our analysis of left distributive left quasigroups with the idempotent case.
Time: Tuesday, November 16. (SC 1403, 2:10 p.m.)
Speaker: David Stanovsky
Title: Non-idempotent left distributive left quasigroups.
Abstract: Left distributive left quasigroups are binary algebras, where all left translations are automorphisms. The main goal of the talk is a description of subdirectly irreducible non-idempotent left distributive left quasigroups.
Time: Thursday, November 11. (SC 1404, 2:30 p.m.)
Speaker: Nikolaos Galatos
Title: Residuated lattices and substructural logics, Part IV.
Abstract: We present two deductive logical systems, one formulated in Gentzen and the second in Hilbert style. We show that these systems are equivalent and that they constitute equivalent algebraic semantics for the class of non-associative residuated lattices. Moreover, we show, in an algebraic way, that the Gentzen system has the cut-elimination property and the Hilbert system has the strong separation property.
Time: Tuesday, November 9. (SC 1403, 2:10 p.m.)
Speaker: Nikolaos Galatos
Title: Residuated lattices and substructural logics, Part III.
Abstract: We present two deductive logical systems, one formulated in Gentzen and the second in Hilbert style. We show that these systems are equivalent and that they constitute equivalent algebraic semantics for the class of non-associative residuated lattices. Moreover, we show, in an algebraic way, that the Gentzen system has the cut-elimination property and the Hilbert system has the strong separation property.
Time: Thursday, November 4. (SC 1404, 2:30 p.m.)
Speaker: Nikolaos Galatos
Title: Residuated lattices and substructural logics, Part II.
Abstract: We present two deductive logical systems, one formulated in Gentzen and the second in Hilbert style. We show that these systems are equivalent and that they constitute equivalent algebraic semantics for the class of non-associative residuated lattices. Moreover, we show, in an algebraic way, that the Gentzen system has the cut-elimination property and the Hilbert system has the strong separation property.
Time: Tuesday, November 2. (SC 1403, 2:10 p.m.)
Speaker: Nikolaos Galatos
Title: Residuated lattices and substructural logics.
Abstract: We present two deductive logical systems, one formulated in Gentzen and the second in Hilbert style. We show that these systems are equivalent and that they constitute equivalent algebraic semantics for the class of non-associative residuated lattices. Moreover, we show, in an algebraic way, that the Gentzen system has the cut-elimination property and the Hilbert system has the strong separation property.
Time: Thursday, October 28. (SC 1404, 2:30 p.m.)
Speaker: Bill Lampe
Title: Some congruence lattice representation problems.
Abstract: The focus will be on the congruence-lattices-of-algebras-having-a-one-element-subalgebra problem and how it relates to other congruence lattice representation problems.
Time: Tuesday, October 26. (SC 1403, 2:10 p.m.)
Speaker: Constantine Tsinakis
Title: An extension of W. C. Holland's theorem to residuated lattices, Part II.
Abstract: We present sufficient conditions for a residuated lattice (RL) to be represented as an RL of residuated maps on a chain. In particular, we show that every GBL-algebra satisfying the pre-linearity law and every GMV algebra has such a representation. These results extend W. C. Holland's corresponding result for lattice-ordered groups and require careful analysis of the algebraic closure system of convex subalgebras of an RL.
Time: Thursday, October 21. (SC 1404, 2:30 p.m.)
Speaker: Constantine Tsinakis
Title: An extension of W. C. Holland's theorem to residuated lattices.
Abstract: Let U be the variety of residuated lattices satisfying the identities x/x=x\x=e and (x\y join y\x) meet e = e (the pre-linearity law). We prove that an algebra in U can be represented as a residuated lattice of residuated maps on a chain if and only if it satisfies the identity x(y meet z)w = xyw meet xzw. In particular, every GBL-algebra satisfying the pre-linearity law and every GMV algebra has such a representation. These results extend W. C. Holland's corresponding result for lattice-ordered groups. The proof is based on the fact that the compact element of the algebraic closure system of convex subalgebras of an algebra in U form a relatively normal lattice.
Time: Thursday, October 14. (SC 1404, 2:30 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: We will continue our presentation on finite basis theorems for quasivarieties.
Time: Tuesday, October 12. (SC 1403, 2:10 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: We will continue our presentation on finite basis theorems for quasivarieties.
Time: Thursday, October 7. (SC 1404, 2:30 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: We will continue our presentation on finite basis theorems for quasivarieties.
Time: Tuesday, October 5. (SC 1403, 2:10 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: We will continue our presentation on finite basis theorems for quasivarieties.
Time: Thursday, September 30. (SC 1404, 2:30 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: An element x of a lattice is pseudo-prime if whenever the meet of y and z is zero then either y of z is below x. We will show that for algebraic lattices, PCC is equivalent to the property that the meet of the pseudo-prime elements is zero. Then we will continue our presentation on finite basis theorems for quasivarieties.
Time: Tuesday, September 28. (SC 1403, 2:10 p.m.)
Speaker: Miklos Maroti (joint work with Ralph McKenzie)
Title: Finite basis problems and results for quasivarieties.
Abstract: We offer new proofs and generalizations of two important finite basis theorems of Don Pigozzi and Ross Willard. Our proofs rely on the study of several congruence properties for quasivarieties, including having pseudo-complemented congruence lattices (PCC) and the weak extension principle (WEP). We show that congruence meet semi-distributive varieties have PCC, and relatively congruence distributive quasivarieties have both the PCC and the WEP.
Time: Thursday, September 23. (SC 1404, 2:30 p.m.)
Speaker: Marcin Kozik
Title: Modeling of Turing machine computations in finite algebras.
Abstract: We present a way to model a computation of an arbitrary Turing machine inside a cartesian product of some finite algebra. We follow an approach of Ralph McKenzie and show that, under certain conditions, the set of elements of "full support" corresponds exactly to tape configurations for some computation of the Turing machine.
Time: Tuesday, September 21. (SC 1403, 2:10 p.m.)
Speaker: Ralph McKenzie (joint work with Marcel Jackson)
Title: Interpreting graph colourability in finite semigroups.
Abstract: Ralph McKenzie will be finishing his proof that for the 55-element semigroup S constructed in last Thursday's seminar, the problem to determine of a finite semigroup if it is in HSP(S) is NP-hard.
Time: Thursday, September 16. (SC 1404, 2:30 p.m.)
Speaker: Ralph McKenzie (joint work with Marcel Jackson)
Title: Interpreting graph colourability in finite semigroups.
Abstract: We show that a number of natural membership problems for classes associated with finite semigroups are computationally difficult. In particular, we construct a 55-element semigroup S such that the finite membership problem for the variety of semigroups generated by S interprets the graph 3-colourability problem.
Time: Tuesday, September 14. (SC 1403, 2:10 p.m.)
Speaker: Eric Zenk
Title: Overview of "Subset systems and generalized distributive lattices".
Abstract: A subset system is a rule which picks a family of subsets of each poset, with the feature that (order preserving) images of selected sets are selected. These can be used to describe (possibly infinitary) algebras where the only operations are taking meets and joins of selected sets. The talk will give several examples of subset systems, then briefly indicate the methods one uses to prove things like: the existence of free algebras in some of these categories, the existence and properties of quotients (surjective images), and the existence of limits (i.e., products and equalizers) in these categories.
Time: Thursday, September 9. (SC 1404, 2:30 p.m.)
Speaker: Constantine Tsinakis (joint work withAnnika Wille)
Title: Minimal Varieties of Involutive Residuated Lattices.
Abstract: We establish the existence uncountably many atoms in the subvariety lattice of the variety of involutive residuated lattices. The proof utilizes a construction used in the proof of the corresponding result for residuated lattices and is based on the fact that every residuated lattice with greatest element can be associated in a canonical way with an involutive residuated lattice.
Time: Tuesday, September 7. (SC 1403, 2:10 p.m.)
Speaker: Jaroslav Jezek (joint work with Petar Markovic and David Stanovsky)
Title: Homomorphic images of finite subdirectly irreducible unary algebras.
Abstract: We prove that a finite unary algebra with at least two operation symbols is a homomorphic image of a (finite) subdirectly irreducible algebra if and only if the intersection of all its subalgebras which have at least two elements is nonempty.
Time: Tuesday, September 7. (SC 1403, 2:10 p.m.)
Speaker: Will Funk
Title: Tutorial on residuated lattices
Abstract: We will begin with the presentation of the definition of the variety of residuated lattices and give some examples of well-known algebraic structures which can be regarded as residuated lattices. Some results concerning the congruence lattice of residuated lattices is discussed. Finally we give a brief overview of the relationship between congruences and convex normal subalgebras of residuated lattices.
|