Universal Algebra and Logic
Fall 2006 Seminars
| 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. |
©2024 Vanderbilt University ·
Site Development: University Web Communications