AIC Seminar Series
Map Coloring with Logic
Tim Hinrichs  Stanford University  
Notice: hosted by Richard Waldinger
Date: 20060413 at 16:00
Location: EJ228 (Directions)

Map coloring is a much discussed problem in the constraint satisfaction and logic programming literature. For example, John McCarthys paper entitled "Coloring Maps and the Kowalski Doctrine" shows how to leverage the properties of planar graphs to reorder a particular set of graph coloring axioms so that no backtracking occurs when searching for a coloring. The formulation he uses is the one typically studied in the literature. Perhaps surprisingly, this formulation, which we call the McCarthy formulation, is not the same set of sentences our introductory logic students produce year after year when asked how to state this same problem in firstorder logic. Our conclusion is that the McCarthy formulation, though heavily studied, is not the most natural formulation for the problem. This talk demonstrates how to reformulate the students axioms into the McCarthy axioms, giving users the ability to encode the problem as they please but allow system designers to leverage powerful results in the constraint satisfaction and logic programming literature.
 

inrichs is a Ph.D. student at Stanford University. He studies computational logic: the representation and processing of knowledge in a logical form. Currently he is interested in relationships between some of the most successful applications of logic in computer science: deductive databases, logic programming, constraint satisfaction, and formal verification. He believes that giving a machine the ability to reason about the space of problems confronted in these areas will allow that machine to leverage the techniques of all four areas when solving problems. A machine exhibiting this ability is said to be doing EXTENSIONAL REASONING because the logic underlying all four of these areas is Herbrand logic, i.e. first order syntax and Herbrand semantics.
 

Please arrive at least 10 minutes early in order to sign in and be escorted to the conference room. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the visitors lot in front of Building E, and should follow the instructions by the lobby phone to be escorted to the meeting room. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page.
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 940253493
SRI International is an independent, nonprofit corporation. Privacy policy
