On the Complexity of Entailment for Cumulative Propositional Dependence Logics

• URL: http://arxiv.org/abs/2605.21113v1
• Date: Wed, 20 May 2026 12:46:13 GMT
• Title: On the Complexity of Entailment for Cumulative Propositional Dependence Logics
• Abstract summary: This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics.<n>As recently shown, cumulative logics are famously characterised by SystemC and exactly captured by the cumulative models of Kraus, Lehmann and Magidor.
• Score: 5.3909333359654275
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. As recently shown, cumulative logics are famously characterised by System~C and exactly captured by the cumulative models of Kraus, Lehmann and Magidor. This gives rise to the entailment problem via relational models, which is specifically considered here.

Related papers

• Representation Theorems for Cumulative Propositional Dependence Logics [5.3909333359654275]
  We prove representation theorems for cumulative propositional dependence logic and cumulative propositional logic with team semantics.<n>For propositional dependence logic, we show that System C entailments are exactly captured by cumulative models from Kraus, Lehmann and Magidor.<n>On the other hand, we show that entailment in cumulative propositional logics with team semantics is exactly captured by cumulative and asymmetric models.
  arXiv  Detail & Related papers  (2026-02-24T20:45:01Z)
• On the Complexity and Properties of Preferential Propositional Dependence Logic [3.1952340441132474]
  Preferential team-based reasoning is shown to be cumulative, yet violates SystemP.<n>We show that these characterisations do, surprisingly, not carry over to preferential team-based propositional logic.
  arXiv  Detail & Related papers  (2025-05-13T12:54:59Z)
• On the Logical Content of Logic Programs [0.0]
  This paper introduces a novel perspective on Logic programming (LP) by defining a support'' relation that explicates what a program knows''<n>Results are formalized using the idea of base-extension semantics within proof-theoretic semantics.<n>Our approach offers new insights into the logical foundations of LP and has potential applications in knowledge representation, automated reasoning, and formal verification.
  arXiv  Detail & Related papers  (2025-03-07T11:58:08Z)
• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning [92.76959707441954]
  We introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM reasoning performance.<n>ZebraLogic enables the generation of puzzles with controllable and quantifiable complexity.<n>Our results reveal a significant decline in accuracy as problem complexity grows.
  arXiv  Detail & Related papers  (2025-02-03T06:44:49Z)
• On the Diagram of Thought [20.805936414171892]
  Large Language Models (LLMs) excel at many tasks but often falter on complex problems that require structured, multi-step reasoning.<n>We introduce the Diagram of Thought (DoT), a new framework that enables a single LLM to build and navigate a mental map of its reasoning.
  arXiv  Detail & Related papers  (2024-09-16T07:01:41Z)
• A Primer for Preferential Non-Monotonic Propositional Team Logics [0.0]
  We show that team-based propositional logics naturally give rise to cumulative non-monotonic entailment relations. Motivated by the non-classical interpretation of disjunction in team semantics, we give a precise characterization for preferential models for propositional dependence logic.
  arXiv  Detail & Related papers  (2024-05-11T09:53:15Z)
• A complete logic for causal consistency [0.0]
  We introduce graph types as a tool to examine causal structures over graphs in this model. The properties of graph types are then used to prove completeness for causal consistency of a new causal logic that conservatively extends pomset logic. Using the fact that causal logic conservatively extends pomset logic, we finish by giving a physically-meaningful interpretation of a separating statement between pomset and BV.
  arXiv  Detail & Related papers  (2024-03-14T11:36:53Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs [67.043747188954]
  We propose a structure-modeled textual encoding framework for inductive logical reasoning over KGs. It encodes linearized query structures and entities using pre-trained language models to find answers. We conduct experiments on two inductive logical reasoning datasets and three transductive datasets.
  arXiv  Detail & Related papers  (2023-05-23T01:25:29Z)
• The Transformation Logics [58.35574640378678]
  We introduce a new family of temporal logics designed to balance the trade-off between expressivity and complexity. Key feature is the possibility of defining operators of a new kind that we call transformation operators. We show them to yield logics capable of creating hierarchies of increasing expressivity and complexity.
  arXiv  Detail & Related papers  (2023-04-19T13:24:04Z)
• MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
  We propose a benchmark to investigate models' logical reasoning capabilities in complex real-life scenarios. Based on the multi-hop chain of reasoning, the explanation form includes three main components. We evaluate the current best models' performance on this new explanation form.
  arXiv  Detail & Related papers  (2022-10-22T16:01:13Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.