pith. sign in

arxiv: 2605.21113 · v1 · pith:ODSQNU57new · submitted 2026-05-20 · 💻 cs.LO · cs.AI

On the Complexity of Entailment for Cumulative Propositional Dependence Logics

Kai Sauerwald , Juha Kontinen , Arne Meier This is my paper

Pith reviewed 2026-05-21 01:51 UTC · model grok-4.3

classification 💻 cs.LO cs.AI
keywords entailmentcomplexitydependence logicteam semanticscumulative logicpropositional logicnon-monotonic reasoning
0
0 comments X

The pith

Complexity results are established and proven for entailment in cumulative propositional dependence logic and in cumulative propositional logic under team semantics.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to classify how hard it is to decide whether one formula entails another in cumulative propositional dependence logic, a system that adds dependence atoms to a non-monotonic base, and in the related cumulative propositional logic interpreted with team semantics. These results matter because they tell us the resources needed to automate inference in logics that track both what information is available and which conclusions can be defeated by new facts. A sympathetic reader would care because the work connects dependence logic, which models informational dependence, with cumulative logic, which models defeasible reasoning, and supplies concrete decision bounds for the combined setting.

Core claim

The 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 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.

What carries the argument

Relational models based on cumulative models that satisfy the properties of System C, used to define and decide entailment.

If this is right

  • Entailment decisions reduce to checks against the relational models that capture cumulative properties.
  • The same complexity bounds apply to both the dependence-atom version and the plain team-semantics version.
  • Decision procedures can be built directly from the model-based characterisation of cumulative entailment.
  • The results extend prior work on cumulative logics to these enriched variants while preserving the underlying model relation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The model-based approach could be reused to obtain complexity results for other combinations of team semantics and non-monotonic properties.
  • Upper and lower bounds might transfer to related settings such as conditional logics or other dependence logics without the cumulative restriction.
  • If the complexity turns out to be low, it would support direct implementation of inference engines for dependence-aware non-monotonic reasoning.
  • The characterisation may allow lifting the results to first-order or modal extensions of the same logics.

Load-bearing premise

That entailment in these logics is exactly captured by checking relational cumulative models defined via System C.

What would settle it

A specific pair of formulas where the relational model check predicts entailment but an independent verification shows it does not hold, or where the decision problem falls outside the proven complexity class.

Figures

Figures reproduced from arXiv: 2605.21113 by Arne Meier, Juha Kontinen, Kai Sauerwald.

Figure 1
Figure 1. Figure 1: Landscape of classes of entailment relations. Solid lines denote strict inclusions, and dotted lines denote inclusions, where it is unknown whether the inclusion is strict. For not defined classes, consult SMK (2025). Theorem 11. The following holds: 1. ENT(TPLcuml) ∈ P and is NC1 -hard. 2. SUCCENT(TPLcuml) ∈ Π 𝑝 2 and is ∆ 𝑝 2 -hard under ≤ log m -reductions. Proof. Regarding the first item, similarly as … view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper establishes and proves complexity results for the entailment problem in cumulative propositional dependence logic and for cumulative propositional logic under team semantics. It relies on the known characterization of cumulative logics by System C and the cumulative models of Kraus, Lehmann and Magidor, reducing entailment to reasoning over relational models.

Significance. If the central reductions and proofs are sound, the results would provide precise complexity classifications for entailment in these nonmonotonic team-based logics, bridging dependence logic with classical nonmonotonic reasoning frameworks and enabling potential transfer of complexity techniques.

major comments (1)
  1. [§3] §3: The paper invokes the characterization of cumulative propositional logic with team semantics by KLM cumulative models but does not supply an explicit reduction or proof establishing that the team-semantics entailment relation (evaluated over sets of assignments) coincides with relational entailment over single worlds in a complexity-class-preserving way. This equivalence is load-bearing for the upper and lower bounds derived in §4.
minor comments (1)
  1. [Preliminaries] The notation distinguishing dependence atoms from classical connectives in the team-semantics setting could be introduced more explicitly in the preliminaries to aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness regarding the equivalence between team semantics and KLM relational models. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3: The paper invokes the characterization of cumulative propositional logic with team semantics by KLM cumulative models but does not supply an explicit reduction or proof establishing that the team-semantics entailment relation (evaluated over sets of assignments) coincides with relational entailment over single worlds in a complexity-class-preserving way. This equivalence is load-bearing for the upper and lower bounds derived in §4.

    Authors: We agree that an explicit account of the reduction would strengthen the presentation. While the manuscript relies on the known characterization of cumulative logics by System C and KLM models (as stated in the introduction and §3), we will add a concise paragraph in the revised §3 that sketches the correspondence: a team T satisfies a formula under team semantics if and only if every world in the corresponding KLM cumulative model satisfies the formula under the relational semantics, with the translation being polynomial-time computable and preserving model size up to a linear factor. This ensures that both the upper-bound algorithm (via reduction to relational entailment) and the lower-bound hardness results transfer directly without altering the complexity class. We will also cite the specific recent result establishing the characterization for team semantics to make the foundation fully transparent. revision: yes

Circularity Check

0 steps flagged

No circularity; standard external KLM characterization plus independent complexity proofs

full rationale

The paper invokes the well-known KLM cumulative models (Kraus, Lehmann, Magidor) as an external characterization of System C, which is independent of the present authors and predates the work by decades. Complexity results for entailment under team semantics and dependence logic are then derived separately in the paper. No equations reduce by construction to fitted inputs, no self-citation chain carries the central claim, and no ansatz or renaming is smuggled in. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the prior characterization of cumulative logics by System C and KLM models, taken as given without re-derivation in this work.

axioms (1)
  • domain assumption Cumulative logics are characterised by System C and exactly captured by the cumulative models of Kraus, Lehmann and Magidor.
    Explicitly invoked in the abstract as the foundation for defining the entailment problem via relational models.

pith-pipeline@v0.9.0 · 5575 in / 1088 out tokens · 42628 ms · 2026-05-21T01:51:16.072041+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Brewka, J

    G. Brewka, J. Dix, K. Konolige, Nonmonotonic Reas- oning: An Overview, volume 73 ofCSLI Lecture Notes, CSLI Publications, Stanford, CA, 1997

    work page 1997

  2. [2]

    Makinson, General theory of cumulative inference, in: Proceedings of the 2nd International Workshop on Non-Monotonic Reasoning, Springer-Verlag, Berlin, Heidelberg, 1989, p

    D. Makinson, General theory of cumulative inference, in: Proceedings of the 2nd International Workshop on Non-Monotonic Reasoning, Springer-Verlag, Berlin, Heidelberg, 1989, p. 1–18

    work page 1989

  3. [3]

    Kraus, D

    S. Kraus, D. Lehmann, M. Magidor, Nonmono- tonic reasoning, preferential models and cumulative lo- gics, Artif. Intell. 44 (1990) 167–207. doi: 10.1016/ 0004-3702(90)90101-5

    work page 1990

  4. [4]

    Baumann, H

    R. Baumann, H. Strass, Consequence operators of char- acterization logics – the case of abstract argumentation, in: C. Dodaro, G. Gupta, M. V . Martinez (Eds.), Logic Programming and Nonmonotonic Reasoning, Springer Nature Switzerland, Cham, 2025, pp. 154–166

    work page 2025

  5. [5]

    Denecker, V

    M. Denecker, V . Marek, M. Truszczy´nski, Approxima- tions, Stable Operators, Well-Founded Fixpoints and Applications in Nonmonotonic Reasoning, Springer US, Boston, MA, 2000, pp. 127–144. doi:10.1007/ 978-1-4615-1567-8_6

    work page 2000

  6. [6]

    Yan, Monotonicity in Intensional Contexts: Weaken- ing and Pragmatic Effects under Modals and Attitudes, Ph.D

    J. Yan, Monotonicity in Intensional Contexts: Weaken- ing and Pragmatic Effects under Modals and Attitudes, Ph.D. thesis, University of Amsterdam, 2023

    work page 2023

  7. [7]

    Sauerwald, A

    K. Sauerwald, A. Meier, J. Kontinen, On the Com- plexity and Properties of Preferential Propositional Dependence Logic, in: Proceedings of the 22nd In- ternational Conference on Principles of Knowledge Representation and Reasoning, 2025, pp. 523–533. doi:10.24963/kr.2025/51

    work page doi:10.24963/kr.2025/51 2025

  8. [8]

    Kontinen, A

    J. Kontinen, A. Meier, K. Sauerwald, On the com- plexity and properties of preferential propositional de- pendence logic, in: R. Wassermann, M.-L. Mugnier, F. Baader (Eds.), Proceedings of the 23rd International Conference on Principles of Knowledge Representa- tion and Reasoning, KR 2026, 2026

    work page 2026

  9. [9]

    Hannula, J

    M. Hannula, J. Kontinen, J. Virtema, H. V ollmer, Com- plexity of propositional logics in team semantic, ACM Trans. Comput. Log. 19 (2018) 2:1–2:14

    work page 2018

  10. [10]

    F. Yang, J. Väänänen, Propositional logics of depend- ence, Ann. Pure Appl. Logic 167 (2016) 557–589. doi:10.1016/j.apal.2016.03.003

    work page doi:10.1016/j.apal.2016.03.003 2016

  11. [11]

    D. M. Gabbay, Theoretical foundations for non- monotonic reasoning in expert systems, in: K. R. Apt (Ed.), Logics and Models of Concurrent Systems, volume 13 ofNATO ASI Series, Springer, 1984, pp. 439–457. doi: 10.1007/978-3-642-82453-1\ _15

    work page doi:10.1007/978-3-642-82453-1 1984

  12. [12]

    Shoham, Reasoning About Change: Time and Caus- ation from the Standpoint of Artificial Intelligence, MIT Press, 1988

    Y . Shoham, Reasoning About Change: Time and Caus- ation from the Standpoint of Artificial Intelligence, MIT Press, 1988

    work page 1988

  13. [13]

    J. Dix, D. Makinson, The relationship between klm and mak models for nonmonotonic inference operations, Journal of Logic, Language, and Information 1 (1992) 131–140. URL: http://www.jstor.org/stable/40180016

    work page arXiv 1992

  14. [14]

    Ebbing, P

    J. Ebbing, P. Lohmann, Complexity of model checking for modal dependence logic, in: Proceedings of the 38th Conference on Current Trends in Theory and Prac- tice of Computer Science (SOFSEM 2012), volume 7147 ofLNCS, Springer, 2012, pp. 226–237

    work page 2012

  15. [15]

    S. R. Buss, S. A. Cook, A. Gupta, V . Ramachandran, An optimal parallel algorithm for formula evaluation, SIAM J. Comput. 21 (1992) 755–780

    work page 1992

  16. [16]

    Kern-Isberner, Conditionals in Nonmonotonic Reas- oning and Belief Revision - Considering Conditionals as Agents, volume 2087 ofLNCS, Springer, 2001

    G. Kern-Isberner, Conditionals in Nonmonotonic Reas- oning and Belief Revision - Considering Conditionals as Agents, volume 2087 ofLNCS, Springer, 2001

    work page 2087

  17. [17]

    Lehmann, Another perspective on default reas- oning, Ann

    D. Lehmann, Another perspective on default reas- oning, Ann. Math. Artif. Intell. 15 (1995) 61–82. doi:10.1007/BF01535841

    work page doi:10.1007/bf01535841 1995

  18. [18]

    C. Komo, C. Beierle, Nonmonotonic reasoning from conditional knowledge bases with system W, Ann. Math. Artif. Intell. 90 (2022) 107–144. doi:10.1007/ S10472-021-09777-9. 4

    work page 2022