Two-Variable First-Order Logics over Transitive Structures
| Dates: | 8 February 2012 |
|---|
| Times: | 14:00 - 16:00 |
|---|
| What is it: | Seminar |
|---|
|
|
Speaker: Dr Lidia Tendera. University of Opole, Poland
Host: Ian Pratt-Hartmann
Abstract:
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.
http://www.cs.manchester.ac.uk/Events_subweb/seminars.php
Travel and Contact Information
Find event
Lecture Theatre 1.4
Kilburn Building
Manchester
