Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

22 November 2007, Logic Tea, Luc Segoufin

Speaker: Luc Segoufin
Title: Order invariance over finite structures
Date: Thursday 22 November 2007
Time: 16:00-17:00
Location: Room P.019, Euclides Building, Plantage Muidergracht 24, Amsterdam

In this talk I will consider <-inv-FO, order-invariant first-order, over finite structures. <-inv-FO is the class of first-order formulas that use an extra predicate interpreted as a linear order, but such that the truthness of the formula does not depend on the choice of the linear order. Over 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 then 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.

The Logic Tea homepage can be found at http://www.illc.uva.nl/logic_tea/. For more information, please contact Joel Uckelmann () or Edgar Andrade ().

Please note that this newsitem has been archived, and may contain outdated information or links.