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

Wednesday, May 15, 2019, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: 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.