BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Characterizations of the Expressive Power of Logics over Trees - L
 uc Segoufin (INRIA and ENS\, Cachan)
DTSTART:20100909T140000Z
DTEND:20100909T150000Z
UID:TALK25624@talks.cam.ac.uk
CONTACT:Anuj Dawar
DESCRIPTION:This talk will be about the expressive power of logics over tr
 ees. More\nprecisely we will try to derive expressibility and inexpressibi
 lity\nresults in a generic way.\n\nOur yardstick will be MSO\, and all the
  logical formalisms we will\nconsider can be seen as fragments of MSO (mon
 adic second order logic). \nGiven a logical formalism L\, we will try to s
 ee which of the properties \nexpressible in MSO are also expressible in L 
 by exhibiting a decidable \ncharacterization of L. By this we mean an algo
 rithm deciding whether a \nformula of MSO is equivalent to a formula of L 
 or not.\n\nThis talk will try to survey the known results in this research
  area.\n\n\n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR