Parameterized Complexity of Logic-Based Argumentation in Schaefer's
Framework
- URL: http://arxiv.org/abs/2102.11782v1
- Date: Tue, 23 Feb 2021 16:34:42 GMT
- Title: Parameterized Complexity of Logic-Based Argumentation in Schaefer's
Framework
- Authors: Yasir Mahmood, Arne Meier, Johannes Schmidt
- Abstract summary: We study the propositional variants of the following three computational tasks studied in argumentation.
ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the hierarchy.
Several cases are of very high intractability (paraNP and beyond)
- Score: 1.5469452301122177
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Logic-based argumentation is a well-established formalism modelling
nonmonotonic reasoning. It has been playing a major role in AI for decades,
now. Informally, a set of formulas is the support for a given claim if it is
consistent, subset-minimal, and implies the claim. In such a case, the pair of
the support and the claim together is called an argument. In this paper, we
study the propositional variants of the following three computational tasks
studied in argumentation: ARG (exists a support for a given claim with respect
to a given set of formulas), ARG-Check (is a given set a support for a given
claim), and ARG-Rel (similarly as ARG plus requiring an additionally given
formula to be contained in the support). ARG-Check is complete for the
complexity class DP, and the other two problems are known to be complete for
the second level of the polynomial hierarchy (Parson et al., J. Log. Comput.,
2003) and, accordingly, are highly intractable. Analyzing the reason for this
intractability, we perform a two-dimensional classification: first, we consider
all possible propositional fragments of the problem within Schaefer's framework
(STOC 1978), and then study different parameterizations for each of the
fragment. We identify a list of reasonable structural parameters (size of the
claim, support, knowledge-base) that are connected to the aforementioned
decision problems. Eventually, we thoroughly draw a fine border of
parameterized intractability for each of the problems showing where the
problems are fixed-parameter tractable and when this exactly stops.
Surprisingly, several cases are of very high intractability (paraNP and
beyond).
Related papers
- Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
We develop an algorithm for the complex task of computing the probability of a set of arguments being a complete extension.
An experimental evaluation shows promise of our approach.
arXiv Detail & Related papers (2024-07-06T12:08:38Z) - Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
Argumentation-based systems often lack explainability while supporting decision-making processes.
Counterfactual and semifactual explanations are interpretability techniques.
We show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework.
arXiv Detail & Related papers (2024-05-07T07:27:27Z) - Identification for Tree-shaped Structural Causal Models in Polynomial
Time [1.5151556900495786]
Identifying causal parameters from correlations between nodes is an open problem in artificial intelligence.
In this paper, we study SCMs whose directed component forms a tree.
We present a randomized-time algorithm, which solves the identification problem for tree-shaped SCMs.
arXiv Detail & Related papers (2023-11-23T15:26:29Z) - A Unifying Framework for Learning Argumentation Semantics [50.69905074548764]
We present a novel framework, which uses an Inductive Logic Programming approach to learn the acceptability semantics for several abstract and structured argumentation frameworks in an interpretable way.
Our framework outperforms existing argumentation solvers, thus opening up new future research directions in the area of formal argumentation and human-machine dialogues.
arXiv Detail & Related papers (2023-10-18T20:18:05Z) - Query Structure Modeling for Inductive Logical Reasoning Over Knowledge
Graphs [67.043747188954]
We propose a structure-modeled textual encoding framework for inductive logical reasoning over KGs.
It encodes linearized query structures and entities using pre-trained language models to find answers.
We conduct experiments on two inductive logical reasoning datasets and three transductive datasets.
arXiv Detail & Related papers (2023-05-23T01:25:29Z) - Analytical Solutions for the Inverse Problem within Gradual Semantics [3.957174470017176]
We show how an analytical approach can be used to solve the inverse problem in gradual semantics.
Unlike the current state-of-the-art, such an approach can rapidly find a solution, and is guaranteed to do so.
arXiv Detail & Related papers (2022-03-02T15:55:10Z) - Abstract Reasoning via Logic-guided Generation [65.92805601327649]
Abstract reasoning, i.e., inferring complicated patterns from given observations, is a central building block of artificial general intelligence.
This paper aims to design a framework for the latter approach and bridge the gap between artificial and human intelligence.
We propose logic-guided generation (LoGe), a novel generative DNN framework that reduces abstract reasoning as an optimization problem in propositional logic.
arXiv Detail & Related papers (2021-07-22T07:28:24Z) - Variational Causal Networks: Approximate Bayesian Inference over Causal
Structures [132.74509389517203]
We introduce a parametric variational family modelled by an autoregressive distribution over the space of discrete DAGs.
In experiments, we demonstrate that the proposed variational posterior is able to provide a good approximation of the true posterior.
arXiv Detail & Related papers (2021-06-14T17:52:49Z) - Logic Embeddings for Complex Query Answering [56.25151854231117]
We propose Logic Embeddings, a new approach to embedding complex queries that uses Skolemisation to eliminate existential variables for efficient querying.
We show that Logic Embeddings are competitively fast and accurate in query answering over large, incomplete knowledge graphs, outperform on negation queries, and in particular, provide improved modeling of answer uncertainty.
arXiv Detail & Related papers (2021-02-28T07:52:37Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries.
We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups)
Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
arXiv Detail & Related papers (2020-06-07T14:47:07Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems.
We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
arXiv Detail & Related papers (2020-06-05T10:56:52Z)
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.