Matthias Hoelzel ; Richard Wilke - On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics

lmcs:6501 - Logical Methods in Computer Science, July 30, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:14)2021
On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics

Authors: Matthias Hoelzel ; Richard Wilke

We present syntactic characterisations for the union closed fragments of existential second-order logic and of logics with team semantics. Since union closure is a semantical and undecidable property, the normal form we introduce enables the handling and provides a better understanding of this fragment. We also introduce inclusion-exclusion games that turn out to be precisely the corresponding model-checking games. These games are not only interesting in their own right, but they also are a key factor towards building a bridge between the semantic and syntactic fragments. On the level of logics with team semantics we additionally present restrictions of inclusion-exclusion logic to capture the union closed fragment. Moreover, we define a team based atom that when adding it to first-order logic also precisely captures the union closed fragment of existential second-order logic which answers an open question by Galliani and Hella.


Volume: Volume 17, Issue 3
Published on: July 30, 2021
Accepted on: June 8, 2021
Submitted on: May 25, 2020
Keywords: Computer Science - Logic in Computer Science,03B70,F.4.1


Share

Consultation statistics

This page has been seen 41 times.
This article's PDF has been downloaded 15 times.