Abstract Dialectical Frameworks Well-founded Model

Problem Description

Abstract Dialectical Frameworks (ADFs for short) are a formalism to model argumentation. They consist of statements and one acceptance condition (ac) for each statement. The acceptance conditions are boolean formulas, to denote relations between statements. Each formula has statements as its variables.

The well-founded model now computes all statements, which are necessarily accepted or rejected. The well-founded model is defined via the following "algorithm":

1.) Accept := {}, Reject := {} 2a.) Add each statement s with a valid formula to Accept 2b.) Add each statement s with an unsatisfiable formula to Reject 3.) Replace the accepted variables in all acceptance conditions (i.e. variables in Accept) with the constant true and all rejected variables with false 4.) If new statements have been accepted/rejected in this iteration go to step 2a, else stop.

Complexity-wise, the verification if a given solution is indeed a solution is DP-complete and the problem of computing a solution is NP-easy.

Reference Paper: G. Brewka, S. Ellmauthaler, H. Strass, J. P. Wallner, and S. Woltran, Abstract Dialectical Frameworks Revisited, in IJCAI'13.

Predicates

• Input: statement/1, ac/2

• Output: accept/1, reject/1

Input format

We encode a statement X by statement(X).

The acceptance condition of a statement X is given by ac(X,F) where F is a formula, specified as follows in BNF, with s being a statement:

<F> ::= s | c(v) | c(f) | neg(<F>) | and(<F>,<F>) | or(<F>,<F>) by c(v) and c(f) we denote the truth constants true and false respectively.

Output format

Example(s)

A possible input is:

statement(1). statement(2). statement(3). statement(4). 
ac(1,c(v)). ac(2,1). ac(3,or(neg(3),4). ac(4,c(f)). 

Then a correct result would be:

accept(1). accept(2). reject(4).

Additional sample instances: download

Problem Peculiarities

Type: Optimization Competition: System Track

Notes and Updates

Author(s)

• Authors: Stefan Ellmauthaler, Johannes Wallner
  • Affiliation: DBAI, Vienna University of Technology, Austria