Our seminar series is free and available for anyone to attend. Unless otherwise stated, seminars take place on Wednesday afternoons at 2pm in the Kilburn Building during teaching season.

If you wish to propose a seminar speaker please contact Antoniu Pop.


Two-Variable First-Order Logics over Transitive Structures

  • Speaker:   Dr  Lidia Tendera  (University of Opole, Poland)
  • Host:   Ian Pratt-Hartmann
  • 8th February 2012 at 14:15 in Lecture Theatre 1.4, Kilburn Building
Two prominent decidable fragments of classical first-order logic, namely the two-variables fragment (FO2) and the guarded fragment (GF), cannot express transitivity of a binary relations. This shortage can be replaced by considering special classes of structures, where some distinguished binary predicate letters are required to be transitive.

In the talk we review main results concerning decidability and complexity of the satisfiability problem for FO2 and GF over such structures. In more detail we discuss the so far open case of FO2 with one transitive relation and outline the proof of its decidability.
▲ Up to the top