Bi-Weekly Talk: Richard Wilke: On the Union Closed Fragment of Existential Second-Order Logic

Mittwoch, 15.05.2019, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragender: Richard Wilke


Abstract: We consider formulae of existential second-order logic in one free relational variable. Such a formula can, over finite structures, express any NP definable property of the relation. In the talk we focus on formulae that are closed under unions with respect to their free variable. A question, that arose in logics with team semantics (where one argues about sets of assignments), has motivated our work, but in this talk I will mainly speak about second-order logic. In terminology of second-order logic the question asks whether there is a syntactic characterisation of all union closed formulae. We use a special kind of model-checking game that is suited to deal with formulae with a free relational variable to answer the question positively.