FO = FO3 for Linear Orders with Monotone Binary Relations

12^th November 2019, 11:00
Marie Fortin

Abstract

Star-free propositional dynamic logic is a variant of propositional dynamic logic (PDL) which is expressively equivalent to the 3-variable fragment of first-order logic. It is closely related to Tarski’s calculus of relations, and captures various temporal logics. In this talk, I will present sufficient conditions for star-free PDL and first-order logic to have the same expressive power over a class of linearly ordered structures with unary and binary relations; namely, that all binary relations are “interval-preserving”. This generalizes several results from the literature, in particular, the fact that linear orders, real-time signals, or Mazurkiewicz traces have the 3-variable property.
This is based on a paper presented at ICALP’19.