Seminars and Colloquia

Tuesday, December 09, 2008

12:00 pm

Indexed-Categorical Bottom-up Semantics for Logic Programming

Speaker: Edward Morehouse<br>Abstract: Within first order logic there are fragments that admit a "bottom-up"interpretation corresponding to least term models in the familiar Tarski set semantics. These models arise as least fixed points of an "immediate consequences" operator, which can represent a step in a simple unification-based derivation system. It was shown by Clark in 1979 that such a derivation system is sound and complete for clausal logic. This result is significant because it provides an algorithm to search for proofs.The theory of topoi gives another, category-based model theory for logic that has been studied extensively. Like set semantics, category theory provides for a bottom-up interpretation as well. Following earlier work in categorical syntax, in 1995 Finkelstein, Freyd and Lipton presented a sound and complete categorical proof and model theory for clausal logic programs which is conservative over its set-based counterpart. In 2001, they showed how implication in goals could be added by a passage to indexed categories. Since then the idea of indexing has been used to model additional logic programming features such as universal quantification in goals (Krishnan 2005), constraints and algebraic datatypes (Amato, Lipton, McGrail to appear).

Exley Science Center - ESC 618

Wednesday, April 01, 2009

04:15 pm

Localized Higher-Order Alexander Modules and Higher-Order Degrees

Speaker: John R. Burke<br>Abstract: In this talk, we will define localized higher-order Alexander modules of CW-complexes which are derived from the integral higher-order Alexander modules by using the Ore localization of certain rings. We will then show that these localized higher-order Alexander modules are right modules over P.I.D.s and with certain conditions are torsion modules. We will also define higher-order Alexander polynomials and then define higher-order degrees of these polynomials. We will show that these higher-order degrees are all significant finite integral valued invariants of certain CW-complexes.

Exley Science Center - ESC 638

Wednesday, November 17, 2010

04:15 pm - 06:00 pm

Graph Coloring and Immersions of Complete Graphs

Speaker: Megan Heenehan, Wesleyan UniversityAbstract: One of the interesting open questions in graph coloring is: if a graph is t-chromatic does it contain (in some way) a complete graph on t vertices? Attempts to solve this problem have included looking for subdivisions of complete graphs, minors of complete graphs, and immersions of complete graphs. This talk will focus on graph immersion. We say a graph H is immersed in a graph G if and only if there exists an injection from the vertices of H to the vertices of G for which the images of adjacent elements in H are connected in G by edge disjoint paths. In 2003 Abu-Khzam and Langston conjectured that if a graph G has chromatic number greater than or equal to t, then there is a complete graph on t vertices immersed in G. We will look at the progress that has been made towards proving this conjecture by considering the connectivity of t-immersion-critical graphs. We will also discuss why immersions may be the right approach to this problem.

ESC 638

Wednesday, May 11, 2011

01:15 pm - 03:00 pm

An introduction to model-theoretic forcing

Speaker: Brett Townsend, WesleyanAbstract: Starting in 1969, Abraham Robinson developed a technique of model-theoretic forcing inspired by the work of Paul Cohen in set theory. I will introduce the basics of Robinson9s forcing and explain some of its connections with more traditional model-theoretic topics like omitting types, model completeness, and categoricity.

ESC 638