21 citations · 116 across the 38 of their papers we have counts for
6 papers · 1 filter
Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
Aleksi Anttila, Juha Kontinen, Fan Yang
We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness at…
Logical Approaches to Non-deterministic Polynomial Time over Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring sem…
The flattening operator in team-based logics
Arnaud Durand, Juha Kontinen, Werner Mérian +1
We propose a systematic study of the so-called flattening operator in team semantics. This operator was first introduced by Hodges in 1997, and has not been studied in more detail…
Locally Consistent K-relations: Entailment and Axioms of Functional Dependence
Timon Barlag, Miika Hannula, Juha Kontinen +2
Local consistency arises in diverse areas, including Bayesian statistics, relational databases, and quantum foundations, and so does the notion of functional dependence. We adopt a…
Independence Under Incomplete Information
Miika Hannula, Minna Hirvonen, Juha Kontinen +1
We initiate an investigation how the fundamental concept of independence can be represented effectively in the presence of incomplete information in relational databases. The conce…
Logic and Computation through the Lens of Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexity…