Arrow Research search

Author name cluster

Thomas Linsbichler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

JELIA Conference 2019 Conference Paper

Preprocessing Argumentation Frameworks via Replacement Patterns

  • Wolfgang Dvorák
  • Matti Järvisalo
  • Thomas Linsbichler
  • Andreas Niskanen
  • Stefan Woltran

Abstract A fast-growing research direction in the study of formal argumentation is the development of practical systems for central reasoning problems underlying argumentation. In particular, numerous systems for abstract argumentation frameworks (AF solvers) are available today, covering several argumentation semantics and reasoning tasks. Instead of proposing another algorithmic approach for AF solving, we introduce in this paper distinct AF preprocessing techniques as a solver-independent approach to obtaining performance improvements of AF solvers. We establish a formal framework of replacement patterns to perform local simplifications that are faithful with respect to standard semantics for AFs. Moreover, we provide a collection of concrete replacement patterns. Towards potential applicability, we employ the patterns in a preliminary empirical evaluation of their influence on AF solver performance.

Details

IJCAI Conference 2018 Conference Paper

Novel Algorithms for Abstract Dialectical Frameworks based on Complexity Analysis of Subclasses and SAT Solving

  • Thomas Linsbichler
  • Marco Maratea
  • Andreas Niskanen
  • Johannes P. Wallner
  • Stefan Woltran

Abstract dialectical frameworks (ADFs) constitute one of the most powerful formalisms in abstract argumentation. Their high computational complexity poses, however, certain challenges when designing efficient systems. In this paper, we tackle this issue by (i) analyzing the complexity of ADFs under structural restrictions, (ii) presenting novel algorithms which make use of these insights, and (iii) empirically evaluating a resulting implementation which relies on calls to SAT solvers.

PDF Details

IJCAI Conference 2017 Conference Paper

A General Notion of Equivalence for Abstract Argumentation

  • Ringo Baumann
  • Wolfgang Dvořák
  • Thomas Linsbichler
  • Stefan Woltran

We introduce a parametrized equivalence notion for abstract argumentation that subsumes standard and strong equivalence as corner cases. Under this notion, two argumentation frameworks are equivalent if they deliver the same extensions under any addition of arguments and attacks that do not affect a given set of core arguments. As we will see, this notion of equivalence nicely captures the concept of local simplifications. We provide exact characterizations and complexity results for deciding our new notion of equivalence.

PDF Details

AAAI Conference 2017 Conference Paper

Solving Advanced Argumentation Problems with Answer-Set Programming

  • Gerhard Brewka
  • Martin Diller
  • Georg Heissenberger
  • Thomas Linsbichler
  • Stefan Woltran

Powerful formalisms for abstract argumentation have been proposed. Their complexity is often located beyond NP and ranges up to the third level of the polynomial hierarchy. The combined complexity of Answer-Set Programming (ASP) exactly matches this complexity when programs are restricted to predicates of bounded arity. In this paper, we exploit this coincidence and present novel efficient translations from abstract dialectical frameworks (ADFs) and GRAPPA to ASP. We also empirically compare our approach to other systems for ADF reasoning and report promising results.

PDF Details

ECAI Conference 2016 Conference Paper

A Uniform Account of Realizability in Abstract Argumentation

  • Thomas Linsbichler
  • Jörg Pührer
  • Hannes Strass

We introduce a general framework for analyzing realizability in abstract dialectical frameworks (ADFs) and various of its subclasses. In particular, the framework applies to Dung argumentation frameworks, SETAFs by Nielsen and Parsons, and bipolar ADFs. We present a uniform characterization method for the admissible, complete, preferred and model/stable semantics. We employ this method to devise an algorithm that decides realizability for the mentioned formalisms and semantics; moreover the algorithm allows for constructing a desired knowledge base whenever one exists. The algorithm is built in a modular way and thus easily extensible to new formalisms and semantics. We have implemented our approach in answer set programming, and used the implementation to obtain several novel results on the relative expressiveness of the abovemen-tioned formalisms.

Details

IJCAI Conference 2016 Conference Paper

Investigating the Relationship between Argumentation Semantics via Signatures

  • Paul E. Dunne
  • Christof Spanring
  • Thomas Linsbichler
  • Stefan Woltran

Understanding the relation between different semantics in abstract argumentation is an important issue, not least since such semantics capture the basic ingredients of different approaches to nonmonotonic reasoning. The question we are interested in relates two semantics as follows: What are the necessary and sufficient conditions, such that we can decide, for any two sets of extensions, whether there exists an argumentation framework which has exactly the first extension set under one semantics, and the second extension set under the other semantics. We investigate in total nine argumentation semantics and give a nearly complete landscape of exact characterizations. As we shall argue, such results not only give an account on the independency between semantics, but might also prove useful in argumentation systems by providing guidelines for how to prune the search space.

PDF Details

KR Conference 2016 Conference Paper

On the Functional Completeness of Argumentation Semantics

  • Massimiliano Giacomin
  • Thomas Linsbichler
  • Stefan Woltran

Abstract argumentation frameworks (AFs) are one of the central formalisms in AI; equipped with a wide range of semantics, they have proven useful in several application domains. We contribute to the systematic analysis of semantics for AFs by connecting two recent lines of research – the work on input/output frameworks and the study of the expressiveness of semantics. We do so by considering the following question: given a function describing an input/output behaviour by mapping extensions (resp. labellings) to sets of extensions (resp. labellings), is there an AF with designated input and output arguments realizing this function under a given semantics? For the major semantics we give exact characterizations of the functions which are realizable in this manner.

IJCAI Conference 2015 Conference Paper

An Extension-Based Approach to Belief Revision in Abstract Argumentation

  • Martin Diller
  • Adrian Haret
  • Thomas Linsbichler
  • Stefan R
  • uuml; mmele
  • Stefan Woltran

Argumentation is an inherently dynamic process. Consequently, recent years have witnessed tremendous research efforts towards an understanding of how the seminal AGM theory of belief change can be applied to argumentation, in particular for Dung’s abstract argumentation frameworks (AFs). However, none of the attempts has yet succeeded in handling the natural situation where the revision of an AF is guaranteed to be representable by an AF as well. In this work, we present a generic solution to this problem which applies to many prominent I-maximal argumentation semantics. In order to prove a full representation theorem, we make use of recent advances in both areas of argumentation and belief change. In particular, we utilize the concepts of realizability in argumentation and the notion of compliance as used in Horn revision.

PDF Details

KR Conference 2014 Conference Paper

Characteristics of Multiple Viewpoints in Abstract Argumentation

  • Paul E. Dunne
  • Wolfgang Dvořák
  • Thomas Linsbichler
  • Stefan Woltran

and gives the collection of all possible sets of extensions an AF can possess under semantics σ. We shall focus on several important semantics namely naive, preferred, semistable, stage, stable, and complete semantics (Dung 1995; Verheij 1996; Caminada, Carnielli, and Dunne 2012) and aim at finding simple criteria to decide whether a set S is contained in Σσ. For instance, we will show that each S ∈ Σpref satisfies the condition that for each pair of distinct sets A and B from S there is at least one a ∈ A and b ∈ B such that a, b do not occur together in any set in S. Thus, for instance, S = {{a, b}, {c, d}, {a, c}, {b, d}} is part of the signature Σpref while neither S ∪ {{a, d}} nor S ∪ {{b, c}} are. This fact can be exploited in a search procedure for enumerating preferred extensions: assume for a given AF F, the three extensions from S have already been calculated as preferred extensions of F. The procedure can now restrict the search space to find further extensions of F (if they exist) to sets with at least one argument different from a, b, c, and d. The problem we study here is also essential in many other aspects. First, our results are important for constructing AFs. Indeed, knowing whether a set S is contained in Σσ is a necessary condition which should be checked before actually looking for an AF F which realizes S under σ, i. e. σ(F) = S. This is of high importance when dynamic aspects of argumentation are considered (Falappa et al. 2011). As an example, suppose a framework F possesses as its σ-extensions a set S and one asks for an adaptation of the framework F such that its σ-extensions are given by S ∪ {E}, i. e. one extension is to be added. The addition of E to S may, for instance, be desired by some agent on the grounds that E contains some subset of arguments which it wishes to be collectively accepted by other agents: no extension in S, however, provides support for the subset of interest to be considered justifiable. Furthermore the agent wishing to add E is reluctant to jeopardize the chance of this happening if the modified AF is such that some existing element of S ceases to be an extension: such an outcome being likely to prejudice other agents against agreeing to changes which admit E. Before considering the adapted framework’s structure, it is obviously crucial to know whether an appropriate framework exists at all, i. e. whether S ∪ {E} ∈ Σσ. In a recent paper on revision of AF s (Coste-Marquis et al. 2013), the authors circumvent this issue by allowing revision to result in a set of AFs such that The study of extension-based semantics within the seminal abstract argumentation model of Dung has largely focused on definitional, algorithmic and complexity issues. In contrast, matters relating to comparisons of representational limits, in particular, the extent to which given collections of extensions are expressible within the formalism, have been under-developed. As such, little is known concerning conditions under which a candidate set of subsets of arguments are “realistic” in the sense that they correspond to the extensions of some argumentation framework AF for a semantics of interest. In this paper we present a formal basis for examining extension-based semantics in terms of the sets of extensions that these may express within a single AF. We provide a number of characterization theorems which guarantee the existence of AFs whose set of extensions satisfy specific conditions and derive preliminary complexity results for decision problems that require such characterizations.

ECAI Conference 2014 Conference Paper

Compact Argumentation Frameworks

  • Ringo Baumann
  • Wolfgang Dvorák
  • Thomas Linsbichler
  • Hannes Strass
  • Stefan Woltran

Abstract argumentation frameworks (AFs) are one of the most studied formalisms in AI. In this work, we introduce a certain subclass of AFs which we call compact. Given an extension-based semantics, the corresponding compact AFs are characterized by the feature that each argument of the AF occurs in at least one extension. This not only guarantees a certain notion of fairness; compact AFs are thus also minimal in the sense that no argument can be removed without changing the outcome. We address the following questions in the paper: (1) How are the classes of compact AFs related for different semantics? (2) Under which circumstances can AFs be transformed into equivalent compact ones? (3) Finally, we show that compact AFs are indeed a non-trivial subclass, since the verification problem remains coNP-hard for certain semantics.

Details