"Logics"

Want to capture the "typical" KR logics, including nonmonotonic logics with multiple acceptable belief sets (e.g., Reiter's Default Logic).

Logic

A logic L is a tuple

L = (KB L , BS L , ACC L )

• KB L is a set of well-formed knowledge bases, each being a set (of formulas)

• BS L is a set of possible belief sets, each being a set (of formulas)

• ACC L : KB L → 2 BS L assigns to each knowledge base a set of acceptable belief sets • As in monotonic MCS, information integration via bridge rules

L is called monotonic, if(

• As in Contextual Default Logic, bridge rules (and logics used) can be nonmonotonic

• Unlike in Contextual Default Logic, arbitrary logics can be used

Bridge Rules

L = L 1 , . . . , L n a collection of logics.

L k -bridge rule over L (1 ≤ k ≤ n):

s ← (r 1 : p 1 ), . . . , (r j : p j ), not (r j+1 : p j+1 ), . . Multi-Context Systems, ctd.

Multi-Context SystemA Multi-Context System M = (C 1 , . . . , C n ) consists of contexts C i = (L i , kb i , br i ), i ∈ {1, . . . , n},

where

• each L i is a logic,

• each kb i ∈ KB i is a L i -knowledge base, and

• each br i is a set of L i -bridge rules over M's logics.

M can be nonmonotonic because one of its context logics is AND/OR because a context has nonmonotonic bridge rules.

Example

Consider the multi-context system M = (C 1 , C 2 ), where the contexts are different views of a paper by the authors.

• C 1 :

• L 1 = Classical Logic • kb 1 = { unhappy ⊃ revision } • br 1 = { unhappy ← (2 : work ) } • C 2 : • L 2 = Reiter's Default Logic • kb 2 = { good : accepted/accepted } • br 2 = { work ← (1 : revision), good ← not (1 : unhappy ) }

Acceptable Belief States

• Belief state: sequence of belief sets, one for each context

• Fundamental Question: Which belief states are acceptable?

• Must be based on the knowledge base of a context AND the information accepted in other contexts (if there are appropriate bridge rules)

• Intuition: belief states must be in equilibrium:

The selected belief set for each context C i must be among the acceptable belief sets for C i 's knowledge base together with the heads of C i 's applicable bridge rules.

Acceptable Belief States, ctd.

Applicable Bridge Rules

Let M = (C 1 , . . . , C n ). The bridge rule s ← (r 1 : p 1 ), . . . , (r j : p j ), not (r j+1 : p j+1 ), . . . , not (r m :

p m ) is applicable in belief state S = (S 1 , . . . , S n ) iff (1) p i ∈ S r i (1 ≤ i ≤ j), and (2) p k ∈ S r k (j + 1 ≤ k ≤ m). Equilibrium A belief state S = (S 1 , . . . , S n ) of M is an equilibrium iff for i ∈ {1, . . . , n} S i ∈ ACC i (kb i ∪ {head(r ) | r ∈ br i is applicable in S}). G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 13 / 36

Example (ctd)

Reconsider multi-context system M = (C 1 , C 2 ):

• kb 1 = { unhappy ⊃ revision } (Classical Logic)

• kb 2 = { good : accepted/accepted } (Default Logic)

• br 1 = { unhappy ← (2 : work ) } • br 2 = { work ← (1 : revision), good ← not (1 : unhappy ) }

M has two equilibria:

• E 1 = (Th({unhappy , revision}), Th({work })) and

• E 2 = (Th({unhappy ⊃ revision}), Th({good, accepted}))

G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 14 / 36

• Problem: self-justifying beliefs

• Present e.g. in Autoepistemic Logic:

L rich ⊃ rich

• Other nonmonotonic formalisms are "grounded," e.g.

• Reiter's Default Logic,

• logic programs with Answer Set Semantics (Gelfond & Lifschitz, 91), • ...

• Equilibria of MCSs are possibly ungrounded, e.g. E 1 ; may be wanted or not

• Groundedness can be achieved by restriction to special class of nonmonotonic formalisms

Argumentation Context Systems

Motivation

• Nonmonotonic MCS neglect 2 important aspects:

• What if information provided by different contexts is conflicting?

• What if a context does not only add information?

• ACS provide an answer to these questions.

• Focus on a particular type of local reasoners: argumentation frameworks.

• Goals achieved by introducing mediators.

G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 16 / 36

• Work based on Dung's widely used abstract argumentation frameworks (AFs).

• Abstract approach: arguments un-analyzed, attacks represented in digraph; can be instantiated in many different ways.

• Argument accepted unless attacked by an accepted argument.

• Semantics single out appropriate accepted sets of arguments:

• Grounded extension: accept unattacked args, eliminate args attacked by accepted args, continue until fixpoint reached. • Preferred extension: maximal conflict free set which attacks each of its attackers. • Stable extension: conflict-free set of arguments which attacks each excluded argument.

• (Value based) preferences captured: modify original AF.

Limitations

• No distinction between arguments, meta-arguments, sources of arguments etc.

• Our interest: additional structure and modularity

• Benefits:

• A handle on complexity and diversity

• A natural account of multi-agent argumentation

• Explicit means to model meta-argumentation

Motivating Example: Conference Reviewing Consider model of the paper review process for a conference

• Hierarchy consisting of PC chair, area chairs, reviewers, authors.

• PC chair determines review criteria.

• Area chairs make sure reviewers make fair judgements and eliminate unjustified arguments from reviews.

• Authors give feedback on reviews. Information flow thus cyclic.

• Reviewers exchange arguments in peer-to-peer discussion.

• Area chairs generate a consistent recommendation.

• PC chair takes recommendations as input for final decision.

Need a flexible framework allowing for cyclic structures encompassing different information integration methods. The Short Story

Med 1 A 1

An argumentation module equipped with a mediator, can "listen" to other modules and "talk" to A 1 : sets an argumentation context using a context definition language; handles inconsistency. (1) head s a context expression (to be defined), body atoms arguments p i from a parent argumentation framework.

Context Based Argumentation

First step: a language for representing context:

a, b args; v , v values; r ∈ {skep, cred}; s ∈ {grnd, pref , stab} arg(a) / arg(a) a is a valid (invalid) argument att(a, b) / att(a, b) (a, b) is a valid (invalid) attack a > b a is strictly preferred to b val(a, v ) the value of a is v v > v value v is strictly better than v mode(r )

the reasoning mode is r sem(s) the chosen semantics is s Context C: set of context expressions.

Contexts as Modifiers

What are extensions of AF A under context C?

C transforms A to A C by (in)validating args and attacks appropriately using new argument def:

a b c d Let C = {arg(a), val(b, v 1 ), val(d, v 2 ), v 1 > v 2 , c > b}. A C is: def a b c d G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 25 / 36

Acceptable Extensions

• Transformation handles statements except mode and sem.

• These are captured in the following definition:

Acceptable C-extension

= (E 1 , R 2 , . . . , R k , choice) where • E 1 is a set of context statements for A 1 ; • R i (2 ≤ i ≤ k ) is a set of bridge rules for A 1 based on A i ;

• choice ∈ { sub , sub sk , , maj, maj sk }, where is a strict partial order on {1, . . . , k }.

Mediators, ctd.

Mediator determines consistent context based on

• arguments accepted by parents and

• chosen consistency method.

Acceptable context

Let Med = (E 1 , R 2 , . . . , R k , choice) be a mediator for A 1 based on A 2 , . . . , A k . A context C for A 1 is acceptable wrt. sets of arguments S 2 , . . . ,

S k of A 2 , . . . , A k , if C is a choice-preferred set for (E 1 , R 2 (S 2 ), . . . , R k (S k )).

Here R i (S i ) are the context statements derivable from S i under R i :

{h | h ← a 1 , ..., a j , not b 1 , ..., not b n ∈ R i , each a i ∈ S i , each b m ∈ S i }

The Module Graph

Module graph

Digraph G(F) = (F, E) where

M j → M i in E iff A j is among the A i 1 , . . . , A i k Med i is based on. Med 3 Med 4 Med 1 Med 2 A 1 A 2 A 3 A 4

An argumentation context system Acceptable States

• For each module, pick accepted set of arguments and context

• Must fit together: chosen arguments acceptable given context, chosen context acceptable given chosen arguments of parents

Acceptable state

State S of F:

maps each M i = (A i , Med i ) to S(M i ) = (Acc i , C i ), Acc i a set of arguments of A i , C i a context for A i .

S acceptable, if

• each Acc i is an acceptable C i -extension for A i , and

• each C i is an acceptable context for Med i wrt. all Acc j for which G(F) has an arc M j → M i .

Some Results

• Existence of acceptable states

• Not guaranteed, even without stable semantics and default negation • Guaranteed if F hierarchic and sem(stab) does not occur in any mediator.

• Complexity

• Reasoning tasks related to acceptable states intractable in general.

• Deciding whether ACS F has some acceptable state Σ p 3 -complete.

• Has lower complexity depending on the various parameters and graph structure.

• F hierarchic, modules use grounded semantics and either sub or maj ⇒ acceptable state computable in polynomial time.

• Complexity of C-extensions dominated by underlying argumentation framework.

MMCS: Context Formalisms

• Need updatable logics.

• Need parameterized semantics.

Context formalismA context formalism L is a tuple L = (KB L , BS L , Sem L = {ACC i L }, U L , upd L } • KB L and BS L as before.

• Sem L a set of possible semantics, each ACC i L : KB L → 2 BS L assigns to a KB a set of acceptable belief sets.

• U L a context language with adequate notion of consistency.

• upd L : KB L × 2 U L → KB L × Sem L assigns to a KB and a set of context formulas an updated KB and a semantics.

G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 34 / 36

• Acceptable belief set: E acceptable for KB under context C: E ∈ ACC i (KB ) where upd(KB, C) = (KB , ACC i ).

• Mediator: as in ACS, bridge rules with heads taken from U L and bodies elements of belief sets of parents.

• MMCS: as in ACS, modules consisting of a KB of particular formalism and corresponding mediator connecting to parents.

• Acceptable state: context and belief set for each module such that

Conclusions

• Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs • Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs • Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs • Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs • Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs

Conclusions

• Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs

Conclusions

• Account of recent/ongoing work on multi-context systems.

• Part I: heterogeneous nonmonotonic systems.

• Part II: generalized updates and consistency mechanisms, focus on argumentation.

• Part III: try to capture best of both worlds.

• MCS special case (cum grano salis): updates extensions, no consistency handling

• ACS special case: all formalisms Dung AFs