BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Number of quantifiers in 3-variable logic on linea
 r orders - Lauri Hella (Univeristy of Tampere)
DTSTART;TZID=Europe/London:20250321T140000
DTEND;TZID=Europe/London:20250321T150000
UID:TALK228991AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/228991
DESCRIPTION:Grohe and Schweikardt proved in 2005 that the smal
 lest sentence of 3-variable logic FO^3^ that can s
 eparate a linear order of length n from all shorte
 r linear orders is of length at least O(√n). The b
 est upper bound for the length of such a sentence 
 that we found in the literature is O(n).\n\nIn thi
 s talk I present a new game that characterizes def
 inability by sentences of FO^k^ with n quantifiers
 . Using this game I show that there is a sentence 
 of FO^3^ with 2m+1 quantifiers that is true in a l
 inear order if and only if its length is at least 
 2m(m+1)+1. Furthermore\, I show a matching lower b
 ound result using the game: all linear orders of l
 ength at least 2m(m+1)+1 are equivalent with respe
 ct to all sentences of FO^3^ with at most 2m+1 qua
 ntifiers. The first of these results implies O(√n)
  upper bound for the length of a sentence of FO^3^
  needed for separating linear orders of length n f
 rom shorter linear orders.\n\n(joint work with Ker
 kko Luosto)
LOCATION:SS03\, Computer Laboratory
CONTACT:Anuj Dawar
END:VEVENT
END:VCALENDAR