# On the Complexity and Properties of Preferential Propositional Dependence Logic

arXiv: https://arxiv.org/abs/2505.08522 · HTML: https://mlsanity.com/paper/2505.08522/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 13 May 2025.

## Builds on (most cited first, 9 of 9)

- [On Dependence Logic](https://mlsanity.com/paper/1305.5948/) (2013)
- [Propositional Logics of Dependence](https://mlsanity.com/paper/1412.7998/) (2014)
- [Approximation and Dependence via Multiteam Semantics](https://mlsanity.com/paper/1510.09040/) (2015)
- [Probabilistic team semantics](https://mlsanity.com/paper/1803.02180/) (2018)
- [The Doxastic Interpretation of Team Semantics](https://mlsanity.com/paper/1305.4744/) (2013)
- [A finite axiomatization of conditional independence and inclusion dependencies](https://mlsanity.com/paper/1309.4927/) (2013)
- [Questions and dependency in intuitionistic logic](https://mlsanity.com/paper/1704.01866/) (2017)
- [Polyteam Semantics](https://mlsanity.com/paper/1704.02158/) (2017)
- [Descriptive complexity of real computation and probabilistic independence logic](https://mlsanity.com/paper/2003.00644/) (2020)

## Built on by (most cited first, 1 of 1)

- [On the Complexity of Entailment for Cumulative Propositional Dependence Logics](https://mlsanity.com/paper/2605.21113/) (2026)

## Abstract (arXiv)

This paper considers the complexity and properties of KLM-style preferential reasoning in the setting of propositional logic with team semantics and dependence atoms, also known as propositional dependence logic. Preferential team-based reasoning is shown to be cumulative, yet violates System~P. We give intuitive conditions that fully characterise those cases where preferential propositional dependence logic satisfies System~P. We show that these characterisations do, surprisingly, not carry over to preferential team-based propositional logic. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models. Finally, we present the complexity of preferential team-based reasoning for two natural representations. This includes novel complexity results for classical (non-team-based) preferential reasoning.