M.Sc. Tuomo Lehtonen defends his doctoral thesis "Computational Approaches to Reasoning in Structured Argumentation" on Friday the 16th of June 2023 at 12 o'clock in the University of Helsinki Physicum building, Auditorium E204 (Gustaf Hällströmin katu 2, 2nd floor). His opponent is Professor Henry Prakken (University of Groningen and Utrecht University, Netherlands) and custos Professor Matti Järvisalo (University of Helsinki). The defence will be held in English.
The thesis of Tuomo Lehtonen is a part of research done in the Department of Computer Science and in the Constraint Reasoning and Optimization group at the University of Helsinki. His supervisors have been Professor Matti Järvisalo (University of Helsinki) and Assistant Professor Johannes P. Wallner (Graz University of Technology, Austria).
Computational Approaches to Reasoning in Structured Argumentation
Formal argumentation is a prominent research area within artificial intel- ligence, aiming to capture rational reasoning when faced with conflicting claims. Argumentation has been applied in fields such as law, medicine, debate analysis and explainable artificial intelligence. We focus on struc- tured argumentation formalisms, which are aimed at capturing argumen- tative reasoning starting with a base of (uncertain) knowledge and end- ing with identifying acceptable claims. In particular, we investigate effi- cient approaches to deciding the acceptability of claims as concrete com- putational problems in the context of two central structured formalisms, assumption-based argumentation (ABA) and abstract rule-based argumen- tation (ASPIC+). In both ABA and ASPIC+, arguments for claims are supported by premises (named assumptions in ABA) via a specified in- ference system, and conflicts are identified based on the elements used to support a claim. Notably, the explicit construction of all arguments that a collection of premises and rules gives rise to is not polynomially bounded.
As a main contribution of this thesis, we develop new algorithmic ap- proaches for efficiently computing acceptable claims that leave the con- struction of arguments implicit. We focus on the logic programming and default logic instantiations of ABA, the logic programming instantiation of ABA+ (ABA extended with preferences over assumptions), and an in- stantiation of ASPIC+ with a language consisting of atoms. To avoid the explicit construction of arguments for acceptance in ASPIC+, we establish new characterizations of central semantics which conventionally rely on the construction of arguments. We develop algorithms based on answer set programming (ASP) and propositional satisfiability (SAT) for deciding the acceptance of claims in ABA and ASPIC+, motivated by the success of applying ASP and SAT solvers to various computationally hard problems. We show empirically that our algorithmic approach has significantly better runtime performance and scalability than existing algorithmic approaches. Our results suggest that it is advantageous to avoid the construction of arguments in practical algorithms and to use efficient declarative methods directly on structured argumentation. Implementations of the algorithms developed in the thesis are made available in open source.
Further, we establish the complexity of reasoning problems in ASPIC+ and ABA+ under several semantics. We show that the complexity of deciding the acceptance of claims in ASPIC+ with no preferences under admissible, complete, stable and preferred semantics is the same as the complexity of the corresponding problems in ABA. We prove that when preferences are included under the well-behaved weakest-link principle and elitist ordering in ASPIC+, the complexity of deciding acceptance under stable semantics is higher than without preferences. For ABA+, we show that the complexity of acceptance under stable semantics is the same with and without prefer- ences, but is higher under admissible semantics with preferences included.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-9325-4.
Printed copies will be available on request from Tuomo Lehtonen: tuomo.lehtonen@helsinki.fi.