Brewka, Gerhard
Weighted Abstract Dialectical Frameworks: Extended and Revised Report
Brewka, Gerhard, Pรผhrer, Jรถrg, Strass, Hannes, Wallner, Johannes P., Woltran, Stefan
Abstract Dialectical Frameworks (ADFs) generalize Dung's argumentation frameworks allowing various relationships among arguments to be expressed in a systematic way. We further generalize ADFs so as to accommodate arbitrary acceptance degrees for the arguments. This makes ADFs applicable in domains where both the initial status of arguments and their relationship are only insufficiently specified by Boolean functions. We define all standard ADF semantics for the weighted case, including grounded, preferred and stable semantics. We illustrate our approach using acceptance degrees from the unit interval and show how other valuation structures can be integrated. In each case it is sufficient to specify how the generalized acceptance conditions are represented by formulas, and to specify the information ordering underlying the characteristic ADF operator. We also present complexity results for problems related to weighted ADFs.
Weighted Abstract Dialectical Frameworks
Brewka, Gerhard (Leipzig University) | Strass, Hannes (Leipzig University) | Wallner, Johannes P. (TU Wien) | Woltran, Stefan (TU Wien)
Abstract Dialectical Frameworks (ADFs) generalize Dung's argumentation frameworks allowing various relationships among arguments to be expressed in a systematic way. We further generalize ADFs so as to accommodate arbitrary acceptance degrees for the arguments. This makes ADFs applicable in domains where both the initial status of arguments and their relationship are only insufficiently specified by Boolean functions. We define all standard ADF semantics for the weighted case, including grounded, preferred and stable semantics. We illustrate our approach using acceptance degrees from the unit interval and show how other valuation structures can be integrated. In each case it is sufficient to specify how the generalized acceptance conditions are represented by formulas, and to specify the information ordering underlying the characteristic ADF operator. We also present complexity results for problems related to weighted ADFs.
Measuring Strong Inconsistency
Ulbricht, Markus (Leipzig University) | Thimm, Matthias (University Koblenz-Landau) | Brewka, Gerhard (Leipzig University)
We address the issue of quantitatively assessing the severity of inconsistencies in nonmonotonic frameworks. While measuring inconsistency in classical logics has been investigated for some time now, taking the nonmonotonicity into account poses new challenges. In order to tackle them, we focus on the structure of minimal strongly kb-inconsistent subsets of a knowledge base kb---a generalization of minimal inconsistency to arbitrary, possibly nonmonotonic, frameworks. We propose measures based on this notion and investigate their behavior in a nonmonotonic setting by revisiting existing rationality postulates, analyzing the compliance of the proposed measures with these postulates, and by investigating their computational complexity.
Reactive Multi-Context Systems: Heterogeneous Reasoning in Dynamic Environments
Brewka, Gerhard, Ellmauthaler, Stefan, Gonรงalves, Ricardo, Knorr, Matthias, Leite, Joรฃo, Pรผhrer, Jรถrg
Managed multi-context systems (mMCSs) allow for the integration of heterogeneous knowledge sources in a modular and very general way. They were, however, mainly designed for static scenarios and are therefore not well-suited for dynamic environments in which continuous reasoning over such heterogeneous knowledge with constantly arriving streams of data is necessary. In this paper, we introduce reactive multi-context systems (rMCSs), a framework for reactive reasoning in the presence of heterogeneous knowledge sources and data streams. We show that rMCSs are indeed well-suited for this purpose by illustrating how several typical problems arising in the context of stream reasoning can be handled using them, by showing how inconsistencies possibly occurring in the integration of multiple knowledge sources can be handled, and by arguing that the potential non-determinism of rMCSs can be avoided if needed using an alternative, more skeptical well-founded semantics instead with beneficial computational properties. We also investigate the computational complexity of various reasoning problems related to rMCSs. Finally, we discuss related work, and show that rMCSs do not only generalize mMCSs to dynamic settings, but also capture/extend relevant approaches w.r.t. dynamics in knowledge representation and stream reasoning.
Solving Advanced Argumentation Problems with Answer-Set Programming
Brewka, Gerhard (Universitรคt Leipzig) | Diller, Martin (Technische Universitรคt Wien) | Heissenberger, Georg (Technische Universitรคt Wien) | Linsbichler, Thomas (Technische Universitรคt Wien) | Woltran, Stefan (Technische Universitรคt Wien)
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.
Answer Set Programming: An Introduction to the Special Issue
Brewka, Gerhard (University of Leipzig) | Eiter, Thomas (Technischen Universitรคt Wien) | Truszczynski, Miroslaw (University of Kentucky)
What distinguishes ASP from other declarative paradigms, like satisfiability (SAT) or constraint solving (CSP), is its underlying modeling language and the semantics involved. Problems are specified using logic programminglike rules, with some convenient extensions facilitating compact and readable problem descriptions. Sets of such rules, or answer set programs, come with an intuitive, well-defined and, by now, well-accepted semantics. This semantics has its roots in research in knowledge representation, in particular nonmonotonic reasoning, and avoids the pitfalls of earlier attempts such as the procedural semantics of Prolog based on negation as finite failure. This semantics was originally called the stable-model semantics and was defined for normal logic programs only, that is, programs consisting of rules with a single atom in the head and any finite number of atoms, possibly preceded by default negation, not, in the body. Stable models were later generalized to broader classes of programs, where the semantics can no longer be defined in terms of sets of atoms, which is a natural representation of classical models. Instead, it was defined by means of some sets of literals. For this reason the term answer set was adopted as more adequate (although answer sets also have a straightforward interpretation as models, albeit three-valued ones). Over the last decade or so, ASP has evolved into a vibrant and active research area that produced not only theoretical insights, but also highly effective and useful software tools and interesting and promising applications.
asprin: Customizing Answer Set Preferences without a Headache
Brewka, Gerhard (University of Leipzig) | Delgrande, James (Simon Fraser University) | Romero, Javier (University of Potsdam) | Schaub, Torsten (University of Potsdam)
In this paper we describe asprin, a general, flexible, and extensible framework for handling preferences among the stable models of a logic program. We show how complex preference relations can be specified through user-defined preference types and their arguments. We describe how preference specifications are handled internally by so-called preference programs, which are used for dominance testing. We also give algorithms for computing one, or all, optimal stable models of a logic program. Notably, our algorithms depend on the complexity of the dominance tests and make use of multi-shot answer set solving technology.
Abstract Dialectical Frameworks Revisited
Brewka, Gerhard (Leipzig University) | Strass, Hannes (Leipzig University) | Ellmauthaler, Stefan (Leipzig University) | Wallner, Johannes Peter (Vienna University of Technology) | Woltran, Stefan (Vienna University of Technology)
We present various new concepts and results related to abstract dialectical frameworks (ADFs), a powerful generalization of Dung's argumentation frameworks (AFs). In particular, we show how the existing definitions of stable and preferred semantics which are restricted to the subcase of so-called bipolar ADFs can be improved and generalized to arbitrary frameworks. Furthermore, we introduce preference handling methods for ADFs, allowing for both reasoning with and about preferences. Finally, we present an implementation based on an encoding in answer set programming.