1 citations · 1 across the 8 of their papers we have counts for
8 papers · 1 filter
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…
On the Complexity of Entailment for Cumulative Propositional Dependence Logics
Kai Sauerwald, Juha Kontinen, Arne Meier
This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. As rec…
Representation Theorems for Cumulative Propositional Dependence Logics
Juha Kontinen, Arne Meier, Kai Sauerwald
This paper establishes and proves representation theorems for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. Cumulative logic…
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…
Synchronous Team Semantics for Temporal Logics
Andreas Krebs, Arne Meier, Jonni Virtema +1
We present team semantics for two of the most important linear and branching time specification languages, Linear Temporal Logic (LTL) and Computation Tree Logic (CTL). With team s…
Submodel Enumeration for CTL Is Hard
Nicolas Fröhlich, Arne Meier
Expressing system specifications using Computation Tree Logic (CTL) formulas, formalising programs using Kripke structures, and then model checking the system is an established wor…