Number of quantifiers in 3-variable logic on linear orders

Add to your list(s) Download to your calendar using vCal

• Lauri Hella (Univeristy of Tampere)
• Friday 21 March 2025, 14:00-15:00
• SS03, Computer Laboratory.

If you have a question about this talk, please contact Anuj Dawar.

Grohe and Schweikardt proved in 2005 that the smallest sentence of 3-variable logic FO³ that can separate a linear order of length n from all shorter linear orders is of length at least O(√n). The best upper bound for the length of such a sentence that we found in the literature is O(n).

In this talk I present a new game that characterizes definability by sentences of FO^k with n quantifiers. Using this game I show that there is a sentence of FO³ with 2m+1 quantifiers that is true in a linear order if and only if its length is at least 2m(m+1)+1. Furthermore, I show a matching lower bound result using the game: all linear orders of length at least 2m(m+1)+1 are equivalent with respect to all sentences of FO³ with at most 2m+1 quantifiers. The first of these results implies O(√n) upper bound for the length of a sentence of FO³ needed for separating linear orders of length n from shorter linear orders.

(joint work with Kerkko Luosto)

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• SS03, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.