On Computing Stable Extensions of Abstract Argumentation Frameworks

• URL: http://arxiv.org/abs/2011.01489v6
• Date: Tue, 14 Sep 2021 07:03:40 GMT
• Title: On Computing Stable Extensions of Abstract Argumentation Frameworks
• Authors: Samer Nofal, Amani Abu Jabal, Abdullah Alfarrarjeh, Ismail Hababeh
• Abstract summary: An textitabstract argumentation framework (sc af) is a directed graph $(A,R)$ where $A$ is a set of textitabstract arguments and $Rsubseteq A times A$ is the textitattack relation. We present a thorough, formal validation of a known backtracking algorithm for listing all stable extensions in a given sc af.
• Score: 1.1251593386108185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An \textit{abstract argumentation framework} ({\sc af} for short) is a directed graph $(A,R)$ where $A$ is a set of \textit{abstract arguments} and $R\subseteq A \times A$ is the \textit{attack} relation. Let $H=(A,R)$ be an {\sc af}, $S \subseteq A$ be a set of arguments and $S^+ = \{y \mid \exists x\in S \text{ with }(x,y)\in R\}$. Then, $S$ is a \textit{stable extension} in $H$ if and only if $S^+ = A\setminus S$. In this paper, we present a thorough, formal validation of a known backtracking algorithm for listing all stable extensions in a given {\sc af}.

Related papers

• Mapping the space of quantum expectation values [0.0]
  For a quantum system with Hilbert space $cal H$ of dimension $N$, a basic question is to understand the set $E_S subset mathbbRn$ of points $vece$. A related question is to determine whether a given set of expectation values $vec$ lies in $E_S$.
  arXiv  Detail & Related papers  (2023-10-19T19:17:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• When Variable-Length Codes Meet the Field of Error Detection [0.0]
  In the spirit of citeJK97,N21, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $tau_d,k$. We examine whether those conditions are decidable for a given regular code.
  arXiv  Detail & Related papers  (2022-08-31T08:14:28Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Terminal Embeddings in Sublinear Time [14.959896180728832]
  We show how to pre-process $T$ to obtain an almost linear-space data structure that supports computing the terminal embedding image of any $qinmathbbRd$ in sublinear time. Our main contribution in this work is to give a new data structure for computing terminal embeddings.
  arXiv  Detail & Related papers  (2021-10-17T00:50:52Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• A Note on Rough Set Algebra and Core Regular Double Stone Algebras [0.0]
  In our Main Theorem we show $R_theta$ with $|theta_u| > 1 forall u in U$ to be isomorphic to $TP_E$ and $C_3E$, and that the three CRDSA's are complete and atomic. In our Main Corollary we show explicitly how we can embed such $R_theta$ in $TP_U$, $C_3U$, respectively, $phicirc alpha_r:R_thetahookright
  arXiv  Detail & Related papers  (2021-01-07T00:32:03Z)
• The quantum query complexity of composition with a relation [78.55044112903148]
  Belovs gave a modified version of the negative weight adversary method, $mathrmADV_relpm(f)$. A relation is efficiently verifiable if $mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$.
  arXiv  Detail & Related papers  (2020-04-14T12:07:20Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)
• Some convergent results for Backtracking Gradient Descent method on Banach spaces [0.0]
  bf Theorem. Let $X$ be a Banach space and $f:Xrightarrow mathbbR$ be a $C2$ function. Let $mathcalC$ be the set of critical points of $f$.
  arXiv  Detail & Related papers  (2020-01-16T12:49:42Z)

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.