On the Complexity and Properties of Preferential Propositional Dependence Logic
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908362092838912 |
|---|---|
| author | Sauerwald, Kai Meier, Arne Kontinen, Juha |
| author_facet | Sauerwald, Kai Meier, Arne Kontinen, Juha |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08522 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity and Properties of Preferential Propositional Dependence Logic Sauerwald, Kai Meier, Arne Kontinen, Juha Artificial Intelligence Logic in Computer Science 03B70, 03B62 I.2.3; F.4.1 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. |
| title | On the Complexity and Properties of Preferential Propositional Dependence Logic |
| topic | Artificial Intelligence Logic in Computer Science 03B70, 03B62 I.2.3; F.4.1 |
| url | https://arxiv.org/abs/2505.08522 |