On the Complexity and Properties of Preferential Propositional Dependence Logic
This work addresses foundational issues in logical reasoning for AI and knowledge representation, though it is incremental in extending preferential reasoning to dependence logic.
The paper investigates the complexity and properties of preferential reasoning in propositional dependence logic with team semantics, showing that it is cumulative but violates System P, and provides conditions for when it satisfies System P, with novel complexity results for classical preferential reasoning.
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.