Computer Science Graduate Seminar: Fragments of Existential Second-Order Logic and Logics with Team Semantics

 

Tuesday, December 10, 2019, 12:00pm

Location: Room 9222, E3 building, Ahornstr. 55

Speaker: Matthias Hoelzel, M.Sc. (Mathematical Foundations of Computer Science - i7)

Abstract:

Team semantics is the modern basis for logics of dependence and independence whose formulae are not evaluated with single assignments, but with sets of such assignments. We study different fragments of logics with team semantics and existential second-order logic (ESO) such as the union-closed fragments of these logics, inclusion logic of restricted arity and logics with team semantics using weaker dependency concepts.

We will present syntactic characterisations for the union-closed fragment of ESO and inclusion-exclusion logic. In order to obtain these characterisation results, novel inclusion-exclusion games are utilised as a bridge between semantical and syntactical fragments. These games are not only the model-checking games of ESO-sentences, but they can also be adapted for fragments of ESO and give rise to the definition of a single team-based atom that captures the union-closed fragment.

Further we answer an open question due to Rönnholm regarding the connection between inclusion logic of restricted arity and a fragment of greatest fixed-point logic.

Finally, we study variants of logics with dependency concepts, which can distinguish elements only up to a given equivalence. We juxtapose these new logics with equivalent fragments of ESO and analyse their expressive powers.

 

The computer science lecturers invite interested people to join.