Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.25
URN: urn:nbn:de:0030-drops-116681
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11668/
Hoelzel, Matthias ; Wilke, Richard
On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{hoelzel_et_al:LIPIcs:2020:11668,
author = {Matthias Hoelzel and Richard Wilke},
title = {{On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics}},
booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-132-0},
ISSN = {1868-8969},
year = {2020},
volume = {152},
editor = {Maribel Fern{\'a}ndez and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11668},
URN = {urn:nbn:de:0030-drops-116681},
doi = {10.4230/LIPIcs.CSL.2020.25},
annote = {Keywords: Higher order logic, Existential second-order logic, Team semantics, Closure properties, Union closure, Model-checking games, Syntactic charactisation}
}
| Keywords: | Higher order logic, Existential second-order logic, Team semantics, Closure properties, Union closure, Model-checking games, Syntactic charactisation | |
| Seminar: | 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 06.01.2020 |
