Safe Dependency Atoms and Possibility Operators in Team Semantics

Pietro Galliani
(Free University of Bozen-Bolzano)

I consider the question of which dependencies are safe for a Team Semantics-based logic FO(D), in the sense that they do not increase its expressive power over sentences when added to it. I show that some dependencies, like totality, non-constancy and non-emptiness, are safe for all logics FO(D), and that other dependencies, like constancy, are not safe for FO(D) for some choices of D despite being strongly first order. I furthermore show that the possibility operator, which holds in a team if and only if its argument holds in some nonempty subteam, can be added to any logic FO(D) without increasing its expressive power over sentences.

In Andrea Orlandini and Martin Zimmermann: Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2018), Saarbrücken, Germany, 26-28th September 2018, Electronic Proceedings in Theoretical Computer Science 277, pp. 58–72.
Published: 7th September 2018.

ArXived at: https://dx.doi.org/10.4204/EPTCS.277.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org