Results 1 to 10 of about 1,485,809 (311)
Tractability Frontier of Data Complexity in Team Semantics [PDF]
Electronic Proceedings in Theoretical Computer Science, 2015 We study the data complexity of model-checking for logics with team semantics. For dependence and independence logic, we completely characterize the tractability/intractability frontier of data complexity of both quantifier-free and quantified formulas ...
Arnaud Durand +3 more
doaj +14 more sources
On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics [PDF]
Logical Methods in Computer Science, 2021 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
Matthias Hoelzel, Richard Wilke
doaj +13 more sources
Decidability of predicate logics with team semantics [PDF]
International Symposium on Mathematical Foundations of Computer Science, 2014 We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIME-complete.
Juha Kontinen +2 more
core +11 more sources
Safe Dependency Atoms and Possibility Operators in Team Semantics [PDF]
Electronic Proceedings in Theoretical Computer Science, 2018 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.
Pietro Galliani
doaj +11 more sources
Unified Foundations of Team Semantics via Semirings [PDF]
Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning, 2023 Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for studying logics of dependence and independence in diverse contexts such as ...
Timon Barlag +4 more
semanticscholar +8 more sources
Compactness in team semantics [PDF]
Mathematical Logic Quarterly, 2022 We provide two proofs of the compactness theorem for extensions of first‐order logic based on team semantics. First, we build upon Lück's [16] ultraproduct construction for team semantics and prove a suitable version of Łoś' Theorem. Second, we show that
Joni Puljujärvi +1 more
semanticscholar +7 more sources
Temporal Team Semantics Revisited [PDF]
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, 2022 In this paper, we study a novel approach to asynchronous hyperproperties by reconsidering the foundations of temporal team semantics. We consider three logics: , and , which are obtained by adding quantification over so-called time evaluation functions ...
Jens Oliver Gutsfeld +3 more
semanticscholar +5 more sources
Team Semantics for Interventionist Counterfactuals: Observations vs. Interventions [PDF]
Journal of Philosophical Logic, 2020 Team semantics is a highly general framework for logics which describe dependencies and independencies among variables. Typically, the (in)dependencies considered in this context are properties of sets of configurations or data records.
Fausto Barbero, Gabriel Sandu
semanticscholar +5 more sources
Dimension in team semantics [PDF]
Mathematical Structures in Computer Science, 2023 We introduce three measures of complexity for families of sets. Each of the three measures, which we call dimensions, is defined in terms of the minimal number of convex subfamilies that are needed for covering the given family.
Lauri Hella +2 more
openalex +3 more sources
Upwards Closed Dependencies in Team Semantics [PDF]
Electronic Proceedings in Theoretical Computer Science, 2013 We prove that adding upwards closed first-order dependency atoms to first-order logic with team semantics does not increase its expressive power (with respect to sentences), and that the same remains true if we also add constancy atoms. As a consequence,
Pietro Galliani
doaj +4 more sources