Arrow Research search

Author name cluster

Gerhard Brewka

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.

56 papers
2 author rows

Possible papers

56

IJCAI Conference 2021 Conference Paper

Comparing Weak Admissibility Semantics to their Dung-style Counterparts (Extended Abstract)

  • Ringo Baumann
  • Gerhard Brewka
  • Markus Ulbricht

Semantics based on weak admissibility were recently introduced to overcome a problem with self-defeating arguments that has not been solved for more than 25 years. The recursive definition of weak admissibility mainly relies on the notion of a reduct regarding a set E which only contains arguments which are neither in E, nor attacked by E. At first glance the reduct seems to be tailored for the weaker versions of Dung-style semantics only. In this paper we show that standard Dung semantics can be naturally reformulated using the reduct revealing that this concept is already implicit. We further identify a new abstract principle for semantics, so-called modularization describing how to obtain further extensions given an initial one. Its importance for the study of abstract argumentation semantics is shown by its ability to alternatively characterize classical and non-classical semantics.

PDF Details DOI

KR Conference 2020 Conference Paper

Comparing Weak Admissibility Semantics to their Dung-style Counterparts -- Reduct, Modularization, and Strong Equivalence in Abstract Argumentation

  • Ringo Baumann
  • Gerhard Brewka
  • Markus Ulbricht

Semantics based on weak admissibility were recently introduced to overcome a problem with self-defeating arguments that has not been solved for more than 25 years. The recursive definition of weak admissibility mainly relies on the notion of a reduct regarding a set E which only contains arguments which are neither in E, nor attacked by E. At first glance the reduct seems to be tailored for the weaker versions of Dung-style semantics only. In this paper we show that standard Dung semantics can be naturally reformulated using the reduct revealing that this concept is already implicit. We further identify a new abstract principle for semantics, so-called modularization describing how to obtain further extensions given an initial one. Its importance for the study of abstract argumentation semantics is shown by its ability to alternatively characterize classical and non-classical semantics. Moreover, we tackle the notion of strong equivalence via characterizing kernels and give a complete classification of the weak versions regarding well-known properties and postulates known from the literature.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Revisiting the Foundations of Abstract Argumentation – Semantics Based on Weak Admissibility and Weak Defense

  • Ringo Baumann
  • Gerhard Brewka
  • Markus Ulbricht

In his seminal 1995 paper, Dung paved the way for abstract argumentation, a by now major research area in knowledge representation. He pointed out that there is a problematic issue with self-defeating arguments underlying all traditional semantics. A self-defeat occurs if an argument attacks itself either directly or indirectly via an odd attack loop, unless the loop is broken up by some argument attacking the loop from outside. Motivated by the fact that such arguments represent self-contradictory or paradoxical arguments, he asked for reasonable semantics which overcome the problem that such arguments may indeed invalidate any argument they attack. This paper tackles this problem from scratch. More precisely, instead of continuing to use previous concepts defined by Dung we provide new foundations for abstract argumentation, so-called weak admissibility and weak defense. After showing that these key concepts are compatible as in the classical case we introduce new versions of the classical Dung-style semantics including complete, preferred and grounded semantics. We provide a rigorous study of these new concepts including interrelationships as well as the relations to their Dung-style counterparts. The newly introduced semantics overcome the issue with self-defeating arguments, and they are semantically insensitive to syntactic deletions of self-attacking arguments, a special case of self-defeat.

PDF Details

KR Conference 2020 Conference Paper

Syntax Splitting = Relevance + Independence: New Postulates for Nonmonotonic Reasoning From Conditional Belief Bases

  • Gabriele Kern-Isberner
  • Christoph Beierle
  • Gerhard Brewka

Syntax splitting, first introduced by Parikh in 1999, is a natural and desirable property of KR systems. Syntax splitting combines two aspects: it requires that the outcome of a certain epistemic operation should only depend on relevant parts of the underlying knowledge base, where relevance is given a syntactic interpretation (relevance). It also requires that strengthening antecedents by irrelevant information should have no influence on the obtained conclusions (independence). In the context of belief revision the study of syntax splitting already proved useful and led to numerous new insights. In this paper we analyse syntax splitting in a different setting, namely nonmonotonic reasoning based on conditional knowledge bases. More precisely, we analyse inductive inference operators which, like system P, system Z, or the more recent c-inference, generate an inference relation from a conditional knowledge base. We axiomatize the two aforementioned aspects of syntax splitting, relevance and independence, as properties of such inductive inference operators. Our main results show that system P and system Z, whilst satisfying relevance, fail to satisfy independence. C-inference, in contrast, turns out to satisfy both relevance and independence and thus fully complies with syntax splitting.

PDF Details DOI

AAAI Conference 2019 Conference Paper

Extension Removal in Abstract Argumentation – An Axiomatic Approach

  • Ringo Baumann
  • Gerhard Brewka

This paper continues the rather recent line of research on the dynamics of non-monotonic formalisms. In particular, we consider semantic changes in Dung’s abstract argumentation formalism. One of the most studied problems in this context is the so-called enforcing problem which is concerned with manipulating argumentation frameworks (AFs) such that a certain desired set of arguments becomes an extension. Here we study the inverse problem, namely the extension removal problem: is it possible – and if so how – to modify a given argumentation framework in such a way that certain undesired extensions are no longer generated? Analogously to the well known AGM paradigm we develop an axiomatic approach to the removal problem, i. e. a certain set of axioms will determine suitable manipulations. Although contraction (that is, the elimination of a particular belief) is conceptually quite different from extension removal, there are surprisingly deep connections between the two: it turns out that postulates for removal can be directly obtained as reformulations of the AGM contraction postulates. We prove a series of formal results including conditional and unconditional existence and semantical uniqueness of removal operators as well as various impossibility results – and show possible ways out.

PDF Details

JELIA Conference 2019 Conference Paper

Multi-valued GRAPPA

  • Gerhard Brewka
  • Jörg Pührer
  • Stefan Woltran

Abstract Abstract dialectical frameworks (ADFs) are generalizations of Dung’s argumentation frameworks which allow arbitrary relationships among arguments to be expressed. In particular, arguments can not only attack each other, they also may provide support for other arguments and interact in various complex ways. The ADF approach has recently been extended in two different ways. On the one hand, GRAPPA is a framework that applies the key notions underlying ADFs – in particular their operator-based semantics – directly to arbitrary labelled graphs. This allows users to represent argumentation scenarios in their favourite graphical representations without giving up the firm ground of well-defined semantics. On the other hand, ADFs have been further generalized to the multi-valued case to enable fine-grained acceptance values. In this paper we unify these approaches and develop a multi-valued version of GRAPPA combining the advantages of both extensions.

Details

AAAI Conference 2018 Conference Paper

Measuring Strong Inconsistency

  • Markus Ulbricht
  • Matthias Thimm
  • Gerhard Brewka

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 K-inconsistent subsets of a knowledge base K—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.

PDF Details

AAAI Conference 2018 Conference Paper

Weighted Abstract Dialectical Frameworks

  • Gerhard Brewka
  • Hannes Strass
  • Johannes Wallner
  • Stefan Woltran

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.

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

IJCAI Conference 2017 Conference Paper

Strong Inconsistency in Nonmonotonic Reasoning

  • Gerhard Brewka
  • Matthias Thimm
  • Markus Ulbricht

Minimal inconsistent subsets of knowledge bases play an important role in classical logics, most notably for repair and inconsistency measurement. It turns out that for nonmonotonic reasoning a stronger notion is needed. In this paper we develop such a notion, called strong inconsistency. We show that—in an arbitrary logic, monotonic or not—minimal strongly inconsistent subsets play the same role as minimal inconsistent subsets in classical reasoning. In particular, we show that the well-known classical duality between hitting sets of minimal inconsistent subsets and maximal consistent subsets generalizes to arbitrary logics if the strong notion of inconsistency is used. We investigate the complexity of various related reasoning problems and present a generic algorithm for computing minimal strongly inconsistent subsets of a knowledge base. We also demonstrate the potential of our new notion for applications, focusing on repair and inconsistency measurement.

PDF Details

IJCAI Conference 2017 Conference Paper

Strong Syntax Splitting for Iterated Belief Revision

  • Gabriele Kern-Isberner
  • Gerhard Brewka

AGM theory is the most influential formal account of belief revision. Nevertheless, there are some issues with the original proposal. In particular, Parikh has pointed out that completely irrelevant information may be affected in AGM revision. To remedy this, he proposed an additional axiom (P) aiming to capture (ir)relevance by a notion of syntax splitting. In this paper we generalize syntax splitting from logical sentences to epistemic states, a step which is necessary to cover iterated revision. The generalization is based on the notion of marginalization of epistemic states. Furthermore, we study epistemic syntax splitting in the context of ordinal conditional functions. Our approach substantially generalizes the semantical treatment of (P) in terms of faithful preorders recently presented by Peppas and colleagues.

PDF Details

JELIA Conference 2016 Conference Paper

Inconsistency Management in Reactive Multi-context Systems

  • Gerhard Brewka
  • Stefan Ellmauthaler
  • Ricardo Gonçalves 0001
  • Matthias Knorr 0001
  • João Leite 0001
  • Jörg Pührer

Abstract We address the problem of global inconsistency in reactive multi-context systems (rMCSs), a framework for reactive reasoning in the presence of heterogeneous knowledge sources that can deal with continuous input streams. Their semantics is given in terms of equilibria streams. The occurrence of inconsistencies, where rMCSs fail to have an equilibria stream, can render the entire system useless. We discuss various methods for handling this problem, following different strategies such as repairing the rMCS, or even relaxing the notion of equilibria stream so that it can go through inconsistent states.

Details

JELIA Conference 2016 Conference Paper

Measuring Inconsistency in Answer Set Programs

  • Markus Ulbricht 0001
  • Matthias Thimm
  • Gerhard Brewka

Abstract We address the issue of quantitatively assessing the severity of inconsistencies in logic programs under the answer set semantics. While measuring inconsistency in classical logics has been investigated for some time now, taking the non-monotonicity of answer set semantics into account brings new challenges that have to be addressed by reasonable accounts of inconsistency measures. We investigate the behavior of inconsistency in logic programs by revisiting existing rationality postulates for inconsistency measurement and developing novel ones taking non-monotonicity into account. Further, we develop new measures for this setting and investigate their properties.

Details

IJCAI Conference 2016 Conference Paper

Preface

  • Subbarao Kambhampati
  • Gerhard Brewka

IJCAI-2016 is different from earlier conferences in the IJCAI series in various respects. It is the first conference of its kind taking place one year after the last IJCAI (and the first-ever leap year one! ). In our view one of the major roles of the flagship AI conference is to provide a forum for reintegrating diverse subfields of AI. For this reason we decided not to have vertical special tracks this year: that is, special tracks divided along specific subtopics such as knowledge representation, machine learning, planning and the like. We did introduce a horizontal special track, though, namely the AI and Web track. This track was chaired by Evgeniy Gabrilovich and Mausam and represents one of the most exciting current application areas for a broad range of AI techniques.

PDF Details

ECAI Conference 2016 Conference Paper

Translation-Based Revision and Merging for Minimal Horn Reasoning

  • Gerhard Brewka
  • Jean-Guy Mailly
  • Stefan Woltran

In this paper we introduce a new approach for revising and merging consistent Horn formulae under minimal model semantics. Our approach is translation-based in the following sense: we generate a propositional encoding capturing both the syntax of the original Horn formulae (the clauses which appear or not in them) and their semantics (their minimal models). We can then use any classical revision or merging operator to perform belief change on the encoding. The resulting propositional theory is then translated back into a Horn formula. We identify some specific operators which guarantee a particular kind of minimal change. A unique feature of our approach is that it allows us to control whether minimality of change primarily relates to the syntax or to the minimal model semantics of the Horn formula. We give an axiomatic characterization of minimal change on the minimal model for this new setting, and we show that some specific translation-based revision and merging operators satisfy our postulates.

Details

IJCAI Conference 2015 Conference Paper

AGM Meets Abstract Argumentation: Expansion and Revision for Dung Frameworks

  • Ringo Baumann
  • Gerhard Brewka

In this paper we combine two of the most important areas of knowledge representation, namely belief revision and (abstract) argumentation. More precisely, we show how AGM-style expansion and revision operators can be defined for Dung’s abstract argumentation frameworks (AFs). Our approach is based on a reformulation of the original AGM postulates for revision in terms of monotonic consequence relations for AFs. The latter are defined via a new family of logics, called Dung logics, which satisfy the important property that ordinary equivalence in these logics coincides with strong equivalence for the respective argumentation semantics. Based on these logics we define expansion as usual via intersection of models. We show the existence of such operators. This is far from trivial and requires to study realizability in the context of Dung logics. We then study revision operators. We show why standard approaches based on a distance measure on models do not work for AFs and present an operator satisfying all postulates for a specific Dung logic.

PDF Details

AAAI Conference 2015 Conference Paper

asprin: Customizing Answer Set Preferences without a Headache

  • Gerhard Brewka
  • James Delgrande
  • Javier Romero
  • Torsten Schaub

In this paper we describe asprin1, 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.

PDF Details

IS Journal 2014 Journal Article

Generalizations of Dung Frameworks and Their Role in Formal Argumentation

  • Gerhard Brewka
  • Sylwia Polberg
  • Stefan Woltran

This article provides a short survey of some of the most popular abstract argumentation frameworks available today. The authors present the general idea of abstract argumentation, highlighting the role of abstract frameworks in the argumentation process, and review the original Dung frameworks and their semantics. A discussion of generalizations of these frameworks follows, focusing on structures taking preferences and values into account and approaches in which not only attack but also support relations can be modeled. Finally, the authors review the concept of abstract dialectical frameworks, one of the most general systems for abstract argumentation providing a flexible, principled representation of arbitrary argument relations.

Details DOI

ECAI Conference 2014 Conference Paper

GRAPPA: A Semantical Framework for Graph-Based Argument Processing

  • Gerhard Brewka
  • Stefan Woltran

Graphical models are widely used in argumentation to visualize relationships among propositions or arguments. The intuitive meaning of the links in the graphs is typically expressed using labels of various kinds. In this paper we introduce a general semantical framework for assigning a precise meaning to labelled argument graphs which makes them suitable for automatic evaluation. Our approach rests on the notion of explicit acceptance conditions, as first studied in Abstract Dialectical Frameworks (ADFs). The acceptance conditions used here are functions from multisets of labels to truth values. We define various Dung style semantics for argument graphs. We also introduce a pattern language for specifying acceptance functions. Moreover, we show how argument graphs can be compiled to ADFs, thus providing an automatic evaluation tool via existing ADF implementations. Finally, we also discuss complexity issues.

Details

ECAI Conference 2014 Conference Paper

Multi-Context Systems for Reactive Reasoning in Dynamic Environments

  • Gerhard Brewka
  • Stefan Ellmauthaler
  • Jörg Pührer

We show in this paper how managed multi-context systems (mMCS) can be turned into a reactive formalism suitable for continuous reasoning in dynamic environments. We extend mMCS with (abstract) sensors and define the notion of a run of the extended systems. We then show how typical problems arising in online reasoning can be addressed: handling potentially inconsistent sensor input, modeling intelligent forms of forgetting, and controlling the reasoning effort spent by contexts. We also investigate the complexity of some important related decision problems.

Details

IJCAI Conference 2013 Conference Paper

Abstract Dialectical Frameworks Revisited

  • Gerhard Brewka
  • Stefan Ellmauthaler
  • Hannes Strass
  • Johannes Peter Wallner
  • Stefan Woltran

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.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Managed Multi-Context Systems

  • Gerhard Brewka
  • Thomas Eiter
  • Michael Fink
  • Antonius Weinzierl

Multi-context systems (MCS) are a powerful framework for interlinking heterogeneous knowledge sources. They model the flow of information among different reasoning components (called contexts) in a declarative way, using so-called bridge rules, where contexts and bridge rules may be nonmonotonic. We considerably generalize MCS to managed MCS (mMCS): while the original bridge rules can only add information to contexts, our generalization allows arbitrary operations on context knowledge bases to be freely defined, e. g. , deletion or revision operators. The paper motivates and introduces the generalized framework and presents several interesting instances. Furthermore, we consider inconsistency management in mMCS and complexity issues.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Relating the Semantics of Abstract Dialectical Frameworks and Standard AFs

  • Gerhard Brewka
  • Paul E. Dunne
  • Stefan Woltran

One criticism often advanced against abstract argumentation frameworks (AFs), is that these consider only one form of interaction between atomic arguments: specifically that an argument attacks another. Attempts to broaden the class of relationships include bipolar frameworks, where arguments support others, and abstract dialectical frameworks (ADFs). The latter, allow "acceptance'' of an argument, x, to be predicated on a given propositional function, C_x, dependent on the corresponding acceptance of its parents, i. e. those y for which occurs. Although offering a richly expressive formalism subsuming both standard and bipolar AFs, an issue that arises with ADFs is whether this expressiveness is achieved in a manner that would be infeasible within standard AFs. Can the semantics used in ADFs be mapped to some AF semantics? How many arguments are needed in an AF to "simulate'' an ADF? We show that (in a formally defined sense) any ADF can be simulated by an AF of similar size and that this translation can be realised by a polynomial time algorithm.

PDF Details DOI

JELIA Conference 2010 Invited Paper

Nonmonotonic Tools for Argumentation

  • Gerhard Brewka

Abstract Dung’s argumentation frameworks (AFs) have become very popular as semantical tools in argumentation. We discuss a generalization of AFs called abstract dialectical frameworks (ADFs). These frameworks are more flexible in that they allow arbitrary boolean functions to be used for the specification of acceptance conditions for nodes. We present the basic underlying definitions and give an example illustrating why they are useful. More precisely, we show how they can be used to provide a semantical foundation for Gordon, Prakken and Walton’s Carneades model of argumentation, lifting the limitation of this model to acyclic argument graphs.

Details

AAAI Conference 2010 Conference Paper

Representing Preferences Among Sets

  • Gerhard Brewka
  • Miroslaw Truszczynski
  • Stefan Woltran

We study methods to specify preferences among subsets of a set (a universe). The methods we focus on are of two types. The first one assumes the universe comes with a preference relation on its elements and attempts to lift that relation to subsets of the universe. That approach has limited expressivity but results in orderings that capture interesting general preference principles. The second method consists of developing formalisms allowing the user to specify “atomic” improvements, and generating from them preferences on the powerset of the universe. We show that the particular formalism we propose is expressive enough to capture the lifted preference relations of the first approach, and generalizes propositional CP-nets. We discuss the importance of domain-independent methods for specifying preferences on sets for knowledge representation formalisms, selecting the formalism of argumentation frameworks as an illustrative example.

PDF Details

KR Conference 2010 Conference Paper

State Defaults and Ramifications in the Unifying Action Calculus

  • Ringo Baumann
  • Gerhard Brewka
  • Hannes Strass
  • Michael Thielscher
  • Vadim Zaslawski

We present a framework for reasoning about actions that not only solves the frame and ramification problems, but also the state default problem—the problem to determine what normally holds at a given time point. Yet, the framework is general enough not to be tied to a specific time structure. This is achieved as follows: We use effect axioms that draw ideas both from Reiter’s successor state axioms and the nonmonotonic causal theories by Giunchiglia et al. These axioms are formulated in a recently proposed unifying action calculus to guarantee independence of a specific underlying notion of time. Reiter’s default logic is then wrapped around the resulting calculus and plays a key role in solving the ramification as well as the state default problem.

IJCAI Conference 2007 Conference Paper

  • Gerhard Brewka
  • Floris Roelofsen
  • Luciano Serafini

In this paper we introduce a multi-context variant of Reiter's default logic. The logic provides a syntactical counterpart of Roelofsen and Serafini's information chain approach (IJCAI-05), yet has several advantages: it is closer to standard ways of representing nonmonotonic inference and a number of results from that area come for free; it is closer to implementation, in particular the restriction to logic programming gives us a computationally attractive framework; and it allows us to handle a problem with the information chain approach related to skeptical reasoning.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Steven Shapiro
  • Gerhard Brewka

Shapiro et al. , presented a framework for representing goal change in the situation calculus. In that framework, agents adopt a goal when requested to do so (by some agent), and they remain committed to the goal unless the request is cancelled by that agent. A common assumption in the agent theory literature is that achievement goals that are believed to be impossible to achieve should be dropped. In this paper, we incorporate this assumption into Shapiro et al. 's framework, however we go a step further. If an agent believes a goal is impossible to achieve, it is dropped. However, if the agent later believes that it was mistaken about the impossibility of achieving the goal, the agent might readopt the goal. In addition, we consider an agent's goals as a whole when making them compatible with their beliefs, rather than considering them individually.

PDF Details

AAAI Conference 2005 Conference Paper

Prioritized Component Systems

  • Gerhard Brewka

We introduce a flexible framework to specify problem solutions (outcomes) and preferences among them. The proposal combines ideas from answer-set programming (ASP), answer-set optimization (ASO) and CP-nets. The problem domain is structured into components. ASP techniques are used to specify values of components, as well as global (intercomponent) constraints among these values. ASO methods are used to describe preferences among the values of a component and CP-net techniques to represent inter-component dependencies and corresponding preferences.

PDF Details

NMR Workshop 2004 Conference Paper

A rank based description language for qualitative preferences

  • Gerhard Brewka

In this paper we develop a language for representing complex qualitative preferences among problem solutions. We use ranked knowledge bases to represent prioritized goals. A basic preference description, that is a ranked knowledge base together with a preference strategy, defines a preference relation on models which represent problem solutions. Our language allows us to express nested combinations of preference descriptions using various connectives. This gives the user the possibility to represent her preferences in a natural, concise and flexible manner. 1

Details

KR Conference 2004 Conference Paper

Complex Preferences for Answer Set Optimization

  • Gerhard Brewka

The main contribution of this paper is the definition of the preference description language PDL. This language allows us to combine qualitative and quantitative, penalty based preferences in a flexible way. This makes it possible to express complex preferences which are needed in many realistic optimization settings. We show that several preference handling methods described in the literature are special cases of our approach. We also demonstrate that PDL expressions can be compiled to logic programs which can be used as tester programs in a generate-and-improve method for finding optimal answer sets.

IJCAI Conference 2003 Conference Paper

Answer Set Optimization

  • Gerhard Brewka
  • Ilkka Niemela
  • Miroslaw Truszczynski

We investigate the combination of answer set programming and qualitative optimization techniques. Answer set optimization programs (ASO programs) have two parts. The generating program produces answer sets representing possible solutions. The preference program expresses user preferences. It induces a preference relation on the answer sets of based on the degree to which rules are satisfied. We discuss possible applications of ASO programming, give complexity results and propose implementation techniques. We also analyze the relationship between A SO programs and CP-networks.

PDF

JELIA Conference 2002 Conference Paper

Implementing Ordered Disjunction Using Answer Set Solvers for Normal Programs

  • Gerhard Brewka
  • Ilkka Niemelä
  • Tommi Syrjänen

Abstract Logic programs with ordered disjunction ( LPODs ) add a new connective to logic programming. This connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A×B intuitively means: if possible A, but if A is not possible, then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. In this paper we show how LPODs can be implemented using answer set solvers for normal programs. The implementation is based on a generator which produces candidate answer sets and a tester which checks whether a given candidate is maximally preferred and produces a better candidate if it is not. We also discuss the complexity of reasoning tasks based on LPODs.

Details

NMR Workshop 2002 Conference Paper

Logic programming with ordered disjunction

  • Gerhard Brewka

Logic programs with ordered disjunction (LPODs) combine ideas underlying Qualitative Choice Logic [5] and answer set programming. Logic programming under answer set semantics is extended with a new connective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A x B intuitively means: if possible A, but if A is not possible then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. LPODs are useful for applications in design and configuration and can serve as a basis for qualitative decision making.

Details

AAAI Conference 2002 Conference Paper

Logic Programming with Ordered Disjunction

  • Gerhard Brewka

Logic programs with ordered disjunction (LPODs) combine ideas underlying Qualitative Choice Logic (Brewka, Benferhat, & Le Berre 2002) and answer set programming. Logic programming under answer set semantics is extended with a new connective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A × B intuitively means: if possible A, but if A is not possible then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. LPODs are useful for applications in design and configuration and can serve as a basis for qualitative decision making.

PDF Details

AAAI Conference 1994 Conference Paper

Reasoning about Priorities in Default Logic

  • Gerhard Brewka

In this paper we argue that for realistic applications involving default reasoning it is necessary to reason about the priorities of defaults. Existing approaches require the knowledge engineer to explicitly state all relevant priorities which are then handled in an extralogical manner, or they are restricted to priorities based on specificity, neglecting other relevant criteria. We present an approach where priority information can be represented within the logical language. Our approach is based on PDL, a prioritized extension of Reiter’s Default Logic recently proposed by the same author. In PDL the generation of extensions is controlled by an ordering of the defaults. This property is used here in the following way: we first build Reiter extensions of a given default theory. These extensions contain explicit information about the priorities of defaults. We then eliminate every extension E that cannot be reconstructed as a PDL extension based on a default ordering that is compatible with the priority information in E. An example from legal reasoning illustrates the power of our approach.

PDF Details

AAAI Conference 1986 Conference Paper

Tweety–Still Flying: Some Remarks on Abnormal Birds, Applicable Rules and a Default Prover

  • Gerhard Brewka

l’ his paper describes FAULTY, a default prover for a decidable subset of p+edicata calculus. FAULTY is based on McDemtt’ s and Doyle’ s Nonmonotonic Logic I und avoids the wet&known weakness of this logic by a restriction to spe@ic theories, which OTQ sujgcictintfor defuult reasoning purposes, howevet. i%e dafautts ~TQ represented in a way that allows explicit control of their applicabi&ty. By btocking the applicability of a default the problem of interacting defaults can be avoided.

PDF Details