BEGIN:VCALENDAR VERSION:2.0 PRODID:ILLC Website X-WR-TIMEZONE:Europe/Amsterdam BEGIN:VTIMEZONE TZID:Europe/Amsterdam X-LIC-LOCATION:Europe/Amsterdam BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:19700329T020000 RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:19701025T030000 RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:/NewsandEvents/Archives/2007/newsitem/2106/22- November-2007-Logic-Tea-Luc-Segoufin DTSTAMP:20071118T000000 SUMMARY:Logic Tea, Luc Segoufin ATTENDEE;ROLE=Speaker:Luc Segoufin DTSTART;TZID=Europe/Amsterdam:20071122T160000 DTEND;TZID=Europe/Amsterdam:20071122T170000 LOCATION:Room P.019, Euclides Building, Plantage M uidergracht 24, Amsterdam DESCRIPTION:In this talk I will consider <-inv-FO, order-invariant first-order, over finite structur es. <-inv-FO is the class of first-order formulas that use an extra predicate interpreted as a linea r order, but such that the truthness of the formul a does not depend on the choice of the linear orde r. Over arbitrary structures, it is a simple conse quence of Craig Interpolation Theorem to show that <-inv-FO and FO have the same expressive power. O ver finite structures it is possible to show that <-inv-FO express strictly more than FO. I will the n show that over simple strucutres, such as words or trees, <-inv-FO=FO. To achieve this I will intr oduce and use an algebraic characterization of FO over trees. The Logic Tea homepage can be found at http://www.illc.uva.nl/logic_tea/. For more in formation, please contact Joel Uckelmann (juckelma at science.uva.nl) or Edgar Andrade (E.J.AndradeL otero at uva.nl). X-ALT-DESC;FMTTYPE=text/html:\n
\n In this talk I will consider <-inv-FO, order-in variant first-order, over finite structures. <- inv-FO is the class of first-order formulas that u se an extra predicate interpreted as a linear orde r, but such that the truthness of the formula does not depend on the choice of the linear order. Ove r arbitrary structures, it is a simple consequence of Craig Interpolation Theorem to show that <- inv-FO and FO have the same expressive power. Over finite structures it is possible to show that < ;-inv-FO express strictly more than FO. I will th en show that over simple strucutres, such as words or trees, <-inv-FO=FO. To achieve this I will introduce and use an algebraic characterization of FO over trees.\n
\n \n\n
The Logic Tea homepage can be found at\n
http://www.illc.uva.nl/logic_tea/.
\n For more information, please contact\n
Joel Uckelmann (juckelma at science.uva.nl)\n
or Edgar Andrade (E.J.Andrade
Lotero at uva.nl).\n