> Merkliste Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp: E-Artikel; Sonstige Veröffentlichung Titel: On the succinctness of atoms of dependency Beteiligte: Lück, Martin [VerfasserIn]; Vilander, Mikka [VerfasserIn] Erschienen: Braunschweig : Department of Theoretical Computer Science, Technical University of Braunschweig, 2019 Erschienen in: Logical Methods in Computer Science 15 (2019), Nr. 3 Ausgabe: published Version Sprache: Englisch DOI: https://doi.org/10.15488/10367; https://doi.org/10.23638/LMCS-15%283%3a17%292019 ISSN: 1860-5974 Schlagwörter: Dependence atom ; Succinctness ; Team semantics Entstehung: Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen. Beschreibung: Propositional team logic is the propositional analog to first-order team logic. Non-classical atoms of dependence, independence, inclusion, exclusion and anonymity can be expressed in it, but for all atoms except dependence only exponential translations are known. In this paper, we systematically compare their succinctness in the existential fragment, where the splitting disjunction only occurs positively, and in full propositional team logic with unrestricted negation. By introducing a variant of the Ehrenfeucht-Fraïssé game called formula size game into team logic, we obtain exponential lower bounds in the existential fragment for all atoms. In the full fragment, we present polynomial upper bounds also for all atoms. © Martin Lück and Miikka Vilander. Zugangsstatus: Freier Zugang Rechte-/Nutzungshinweise: Namensnennung (CC BY)