7 papers
Aspects of Coherence in Dependence Logic
Timon Barlag, Nicolas Fröhlich, Miika Hannula +4
Dependence logic extends first-order logic with dependence atoms asserting that the value of a variable is determined by the values of certain other variables. The semantics of dep…
Inconsistent Databases and Argumentation Frameworks with Collective Attacks
Yasir Mahmood, Jonni Virtema, Timon Barlag +1
The connection between subset-maximal repairs for inconsistent databases involving various integrity constraints and acceptable sets of arguments within argumentation frameworks ha…
Recurrent Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker +2
We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers. Our networks are not restricted to aggregat…
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…
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…
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 complexit…