Dung-1.1: An implementation of the Dung argumentation frameworks.

Safe HaskellSafe-Inferred
LanguageHaskell98

Language.Dung.AF

Contents

Description

This module implements Dung's argumentation frameworks.

Synopsis

Basic definitions

data DungAF arg Source

An abstract argumentation framework is a set of arguments (represented as a list) and an attack relation on these arguments.

Constructors

AF [arg] [(arg, arg)] 

Instances

Eq arg => Eq (DungAF arg) 
Ord arg => Ord (DungAF arg) 
Show arg => Show (DungAF arg) 

setAttacks :: Eq arg => DungAF arg -> [arg] -> arg -> Bool Source

Given an argumentation framework, determines whether args (subset of the arguments in the AF), attacks an argument arg (in the AF).

aplus :: Eq arg => DungAF arg -> arg -> [arg] Source

Given an argumentation framework, determines the set of arguments that are attacked by an argument (in the AF).

amin :: Eq arg => DungAF arg -> arg -> [arg] Source

Given an argumentation framework, determines the set of arguments attacking an argument (in the AF).

argplus :: Ord arg => DungAF arg -> [arg] -> [arg] Source

Given an argumentation framework, determines the set of arguments that are attacked by the given subset of arguments (in the AF).

argmin :: Ord arg => DungAF arg -> [arg] -> [arg] Source

Given an argumentation framework, determines the set of arguments that attack a given subset of arguments (in the AF).

conflictFree :: Eq arg => DungAF arg -> [arg] -> Bool Source

Given an argumentation framework, determines whether args (subset of the arguments in the AF) is conflict-free.

acceptable :: Eq arg => DungAF arg -> arg -> [arg] -> Bool Source

Given an argumentation framework, determines whether an argument is acceptable with respect to a list of args (subset of the arguments in the AF).

f :: Eq arg => DungAF arg -> [arg] -> [arg] Source

Given an argumentation framework, returns the set of arguments that are acceptable with respect to args (subset of the arguments in the AF).

admissible :: Ord arg => DungAF arg -> [arg] -> Bool Source

Given an argumentation framework, determines whether the set of arguments args (subset of the arguments in the AF) is admissible, i.e. if args is conflictFree and args is a subset of f af args

Grounded, complete, preferred and stable semantics through fixpoints

groundedF :: Eq arg => ([arg] -> [arg]) -> [arg] Source

Given a characteristic function f, computes the grounded extension by iterating on the empty set (list) until it reaches a fixpoint.

groundedF' :: Eq arg => ([arg] -> [arg]) -> [arg] Source

Given a characteristic function f, computes the grounded extension by iterating on the empty set (list) until it reaches a fixpoint. Strict version.

completeF :: Ord arg => DungAF arg -> [[arg]] Source

Given an argumentation framework, computes all complete extension, by taking all sets of arguments of the powerset of arguments of that AF, given that they are admissible and f af == f.

preferredF :: Ord arg => DungAF arg -> [[arg]] Source

Given an argumentation framework, computes all preferred extensions, by applying a filter on the complete extensions. Note that this, naive definition is faster than the current algorithm implementation.

stableF :: Ord arg => DungAF arg -> [[arg]] Source

Given an argumentation framework, computes all stable extensions, by applying a filter on the complete extensions. Note that this, naive definition is faster than the current algorithm implementation.

Definitions of a preferred and stable extension

isPreferredExt :: Ord arg => DungAF arg -> [[arg]] -> [arg] -> Bool Source

A complete extension is also a preferred extension if it is not a subset of one of the other extensions.

isStableExt :: Ord arg => DungAF arg -> [arg] -> Bool Source

S is a stable extension is an extension iff it is equal to the set of arguments not attacked by S.

Basic labelling definitions

The following functions are implementations of the definitions in "An algorithm for Computing Semi-Stable Semantics" in "Symbolic and Quantitative Approaches to Reasoning with Uncertainty", pages 222--234, Springer, 2007.

data Status Source

Labelling status of arguments.

Constructors

In 
Out 
Undecided 

Instances

type Labelling arg = [(arg, Status)] Source

Labelling of arguments.

inLab :: Labelling arg -> [arg] Source

Given a labelling of arguments, give back the arguments labelled In.

outLab :: Labelling arg -> [arg] Source

Given a labelling of arguments, give back the arguments labelled Out.

undecLab :: Labelling arg -> [arg] Source

Given a labelling of arguments, give back the arguments labelled Undecided.

allIn :: [arg] -> Labelling arg Source

The allIn labelling is a Labelling that labels every argument In.

allOut :: [arg] -> Labelling arg Source

The allOut labelling is a Labelling that labels every argument Out.

allUndec :: [arg] -> Labelling arg Source

The allUndec labelling is a Labelling that labels every argument Undecided.

powerLabel :: [arg] -> [Labelling arg] Source

Computes a list with all possible labellings.

unattacked :: Ord arg => [arg] -> DungAF arg -> arg -> Bool Source

Given a list of arguments that are Out in an argumentation framework af, an argument arg is unattacked if the list of its attackers, ignoring the outs, is empty.

attacked :: Ord arg => [arg] -> DungAF arg -> arg -> Bool Source

Given a list of arguments that are In in an argumentation framework af, an argument arg is attacked if there exists an attacker that is In.

labAttackers :: Eq arg => DungAF arg -> arg -> Labelling arg -> Labelling arg Source

Given an argumentation framework, determines the list of attackers of an argument, from a given labelling, returning the labelled attackers.

illegallyIn :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is illegally In iff a is labelled In, but not all its attackers are labelled Out.

illegallyOut :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is illegally Out iff a is labelled Out but does not have an attacker labelled In.

illegallyUndec :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is illegally Undecided iff a is labelled Undecided but either all its attackers are labelled Out or it has an attacker that is labelled In.

legallyIn :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is legally In iff a is labelled In and it's not illegallyIn.

legallyOut :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is legally Out iff a is labelled Out and it's not illegallyOut.

legallyUndec :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is legally Undecided iff a is labelled Undecided and it's not illegallyUndec.

isAdmissible :: Eq arg => DungAF arg -> Labelling arg -> Bool Source

Given an AF, an admissible labelling is a Labelling without arguments that are illegallyIn and without arguments that are illegallyOut.

isComplete :: Eq arg => DungAF arg -> Labelling arg -> Bool Source

Given an AF, a complete labelling is a labelling without arguments that are illegallyIn, without arguments that are illegallyOut and without arguments that are illegallyUndec.

isPreferred :: Ord arg => DungAF arg -> [Labelling arg] -> Labelling arg -> Bool Source

Let labs be a complete labelling, i.e. isComplete af labs, we say that labs is a preferred labelling iff inLab labs is maximal (w.r.t. set inclusion).

isStable :: Eq arg => DungAF arg -> [Labelling arg] -> Labelling arg -> Bool Source

Let labs be a complete labelling, i.e. 'isComplete af labs', we say that labs is a preferred labelling iff undecLab(labs) == []

isSemiStable :: Ord arg => DungAF arg -> [Labelling arg] -> Labelling arg -> Bool Source

Let labs be a complete labelling, i.e. isComplete af labs, we say that labs is a semi-stable labelling iff undecLab labs is minimal (w.r.t. set inclusion).

transitionStep :: Eq arg => DungAF arg -> Labelling arg -> arg -> Labelling arg Source

Given an AF, a labelling labs and an illegally in argument a in the af, (i.e. illegallyIn af a labs => True), a transition step on a in labs consists of the following: 1. the label of a is changed from In to Out 2. for every b in {a} cup a+, if b is illegally out, then change the label from b from Out to Undecided

terminatedTransition :: Eq arg => DungAF arg -> Labelling arg -> Bool Source

Given an AF, a labelling, labs, is terminated iff labs does not contain any argument that is illegally in, i.e. not (illegallyIn af lab arg) for all arg in labs.

superIllegallyIn :: Eq arg => DungAF arg -> Labelling arg -> (arg, Status) -> Bool Source

Given an AF and Labelling, an argument a (in the AF) is superillegally In iff a is labelled In, and it is attacked by an argument that is legally In or legally Undecided.

Grounded, preferred, semi-stable and stable labellings

The following functions are implementations of the definitions in "An algorithm for Computing Semi-Stable Semantics" in "Symbolic and Quantitative Approaches to Reasoning with Uncertainty", pages 222--234, Springer, 2007 and Section 4.1 of Proof Theories and Algorithms for Abstract Argumentation Frameworks by Modgil and Caminada.

grounded :: Ord arg => DungAF arg -> Labelling arg Source

Computes the grounded labelling for a Dung argumentation framework, returning a (unique) list of arguments with statuses.

Based on section 4.1 of Proof Theories and Algorithms for Abstract Argumentation Frameworks by Modgil and Caminada.

groundedExt :: Ord arg => DungAF arg -> [arg] Source

The grounded extension of an argumentation framework is just the grounded labelling, keeping only those arguments that were labelled In.

complete :: Ord arg => DungAF arg -> [Labelling arg] Source

Computes maximal and minimal complete labellings for a Dung argumentation framework. This is based on Caminada's algorithm for computing semi-stable labellings, with all checks removed.

preferred :: Ord arg => DungAF arg -> [Labelling arg] Source

Computes all preferred labellings for a Dung argumentation framework, by taking the maximally in complete labellings.

stable :: Ord arg => DungAF arg -> [Labelling arg] Source

Computes all stable labellings for a Dung argumentation framework, by keeping only those labellings with no Undecided labels.

semiStable :: Ord arg => DungAF arg -> [Labelling arg] Source

Computes all semi-stable labellings for a Dung argumentation framework, by taking the minimally undecided complete labellings.

completeExt :: Ord arg => DungAF arg -> [[arg]] Source

The complete extension of an argumentation framework is just the complete labelling, keeping only those arguments that were labelled In.

preferredExt :: Ord arg => DungAF arg -> [[arg]] Source

The preferred extension of an argumentation framework is just the preferred labelling, keeping only those arguments that were labelled In.

stableExt :: Ord arg => DungAF arg -> [[arg]] Source

The stable extension of an argumentation framework is just the stable labelling, keeping only those arguments that were labelled In.

semiStableExt :: Ord arg => DungAF arg -> [[arg]] Source

The semi-stable extension of an argumentation framework is just the semi-stable labelling, keeping only those arguments that were labelled In.