8 papers
Approximate Functional Dependencies---Implication Problem Revisited
Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen +1
Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data o…
Expressibility and inexpressibility in propositional team logics
Matilda Häggblom, Minna Hirvonen, Jouko Väänänen
We develop dimension theoretic methods for propositional team based logics. Such quantitative methods were defined for team based first-order logic in a recent paper by Hella, Luos…
Implication Problems over Positive Semirings
Minna Hirvonen
We study various notions of dependency in semiring team semantics. Semiring teams are essentially database relations, where each tuple is annotated with some element from a positiv…
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…
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…
Logics with probabilistic team semantics and the Boolean negation
Miika Hannula, Minna Hirvonen, Juha Kontinen +3
We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic ind…
On elementary logics for quantitative dependencies
Miika Hannula, Minna Hirvonen, Juha Kontinen
We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable…