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 SemanticsArticle

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

    Consultation statistics

    This page has been seen 1697 times.
    This article's PDF has been downloaded 266 times.