Search |  Contact |  SRI Home Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation.

AIC Seminar Series

Map Coloring with Logic

Tim HinrichsStanford University

Notice:  hosted by Richard Waldinger

Date:  2006-04-13 at 16:00

Location:  EJ228  (Directions)

   Abstract

Map coloring is a much discussed problem in the constraint satisfaction and logic programming literature. For example, John McCarthy’s 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 first-order 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.

   Bio for Tim Hinrichs

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.

   Note for Visitors to SRI

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.

SRI International
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy