1 citations · 1 across the 8 of their papers we have counts for
3 papers · 2 filters
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…
Disjunctions of Two Dependence Atoms
Nicolas Fröhlich, Phokion G. Kolaitis, Arne Meier
Dependence logic is a formalism that augments the syntax of first-order logic with dependence atoms asserting that the value of a variable is determined by the values of some other…
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…