On the Complexity and Properties of Preferential Propositional Dependence Logic

• URL: http://arxiv.org/abs/2505.08522v1
• Date: Tue, 13 May 2025 12:54:59 GMT
• Title: On the Complexity and Properties of Preferential Propositional Dependence Logic
• Authors: Kai Sauerwald, Arne Meier, Juha Kontinen,
• Abstract summary: 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.
• Score: 3.1952340441132474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Interleaving Logic and Counting [5.71869130799784]
  Reasoning with quantifier expressions in natural language combines logical and arithmetical features.<n>Our topic is this cooperation of styles as it occurs in common linguistic usage.
  arXiv  Detail & Related papers  (2025-07-07T17:30:29Z)
• 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)
• 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)
• 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)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  Passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence) We propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs) The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features.
  arXiv  Detail & Related papers  (2022-07-04T14:38:49Z)
• Strong Equivalence of Logic Programs with Ordered Disjunction: a Logical Perspective [1.160208922584163]
  Logic Programs with Ordered Disjunction (LPODs) extend classical logic programs with the capability of expressing preferential disjunctions. In this paper we obtain a purely logical characterization of strong equivalence of LPODs as logical equivalence in a four-valued logic. We provide a new proof of the coNP-completeness of strong equivalence for LPODs, which has an interest in its own right since it relies on the special structure of such programs.
  arXiv  Detail & Related papers  (2022-05-10T13:33:32Z)
• A Formalisation of Abstract Argumentation in Higher-Order Logic [77.34726150561087]
  We present an approach for representing abstract argumentation frameworks based on an encoding into classical higher-order logic. This provides a uniform framework for computer-assisted assessment of abstract argumentation frameworks using interactive and automated reasoning tools.
  arXiv  Detail & Related papers  (2021-10-18T10:45:59Z)
• Sequent-Type Calculi for Systems of Nonmonotonic Paraconsistent Logics [2.627046865670577]
  We introduce uniform axiomatisations for a family of nonmonotonic paraconsistent logics based on minimal inconsistency in terms of sequent-type proof systems. We provide sequent-type calculi for Priest's three-valued minimally inconsistent logic of paradox, and for four-valued paraconsistent inference relations due to Arieli and Avron.
  arXiv  Detail & Related papers  (2020-09-22T00:49:52Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  We give a sound and strongly complete axiomatization that can be parametrized to cover essentially every real-valued logic. Our class of sentences are very rich, and each describes a set of possible real values for a collection of formulas of the real-valued logic.
  arXiv  Detail & Related papers  (2020-08-06T02:13:11Z)

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.