BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/2106/22-November-2007-Logic-Tea-Luc-Segoufin
DTSTAMP:20071118T000000
SUMMARY:Logic Tea, Luc Segoufin
ATTENDEE;ROLE=Speaker:Luc Segoufin
DTSTART:20071122T160000
DTEND: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
~~

~~\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/2106/22-November-2007-Logic-Tea-Luc-Segoufin
END:VEVENT
END:VCALENDAR
~~