Two-Variable First-Order Logics over Transitive Structures
Lidia Tendera (Opole Univeristy)
Info
|
Date |
1st May 2012 (week 2, Trinity Term 2012) |
|
Time |
11:30 |
|
Place |
147 |
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 (this is joint work with Wiesław Szwast).
Further info
|
Related series |
|
