Revision of Argumentation Frameworks

Abstract Top of the page

This webpage is dedicated to the experimentations related to the work realized about the adaptation of belief revision [1], [11], [12] in the framework of abstract argumentation [10].
The work currently presented here is the implementation of the first step of the revision operators defined in [9].

exemple of AF

The topic of dynamics of argumentation frameworks has been very studied in recent years (see, for example, [2], [4], [5], [6], [8] or [13]).
Our work differs from the previous ones in at least two points:

the characterisation of revision operators through AGM-like postulates;
the change allowed: modification of the attack relation, with no addition of new argument, and minimal change on arguments statutses.

The work presented here is still in progress, and so the webpage will be updated as often as required/possible.
For more details, any question or remark, do not hesitate to join us: {coste, konieczny, mailly, marquis}@cril.fr

The DynArgs software (v0.1) Top of the page

DynArgs is written in Java, so as to any computer with a Java Runtime Environment can run it. Some procedures use a Sat-based approach, with Sat4j library [14]. Our encoding is based on the work from [3].
The software DynArgs is still in development. It will be available for download as soon as possible, with the minimal compliance level and every information required to use it.
Even if the software is not yet available for download, we can present its global behaviour and the first experimental results.

Input Files Format Top of the page

AFs revision software needs two inputs:

an argumentation framework,
and a revision formula.

For each input file, two formats are possible.
First, for the AF, the format from ASPARTIX project is available:

Example:

arg(a).
arg(b).
arg(c).
att(a,b).
att(b,a).
att(b,c).

Another format accepted is a matrix format, where the attack graph is represented as a binary matrix.
A 0 at the nth line and mth column means that there is no attack from argument n to argument m, 1 means that the attack exists. The first line gives the number of arguments.

Example:

3
0 1 0
1 0 1
0 0 1

The revision formula can be given in two different formats. First, the standard DIMACS format to represent a CNF formula.

Example:

p cnf 5 5
4 -5 0
5 3 2 0
-4 -1 0
5 -2 0
-5 2 0

Then, the formula can be given in a more readable format:

Example:

or 1 not and 2 3

represents the formula 1 or (not (2 and 3)) in prefixe notation.

Current Features Top of the page

In the current state, DynArgs performs the logical revision of stable extensions of an AF, with the Hamming distance-based revision operator described in [9].
The first future work is to encode generation operators defined in the paper to be able to perform a full revision of an AF. Other future work is to take advandage of labellings [7] and to implement the labelling-based operators defined in the paper.

Experimental Results Top of the page

Here are some experimental results, conducted on the CRIL cluster:

Average Time to Compute Revised Stable Extensions
Size of AFs	Average Time (ms)
20 arguments	456.32608695652175
30 arguments	676.0227272727273
50 arguments	5761.3707865168535
70 arguments	47401.68115942029

Bibliography Top of the page

[1]	Carlos E. Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change : Partial meet contraction and revision functions. Journal of Symbolic Logic, 50:510-530, 1985.
[2]	Ringo Baumann. What does it take to enforce an argument? minimal change in abstract argumentation. In Proceedings of the European Conference on Artificial Intelligence (ECAI'12), pages 127-132, 2012.
[3]	Philippe Besnard and Sylvie Doutre. Checking the acceptability of a set of arguments. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR'04), pages 59-64, 2004.
[4]	Pierre Bisquert, Claudette Cayrol, Florence Dupin de Saint-Cyr, and Marie-Christine Lagasquie-Schiex. Change in argumentation systems: Exploring the interest of removing an argument. In Proceedings of the International Conference on Scalable Uncertainty Management (SUM'11), volume 6929 of Lecture Notes in Computer Science, pages 275-288. Springer, 2011.
[5]	Guido Boella, Souhila Kaci, and Leendert van der Torre. Dynamics in argumentation with single extensions: attack refinement and the grounded extension. In Proceedings of the International Conference on Autonomous Agents and Multiagents Systems (AAMAS'09), pages 1213-1214, 2009.
[6]	Guido Boella, Souhila Kaci, and Leendert van der Torre. Dynamics in argumentation with single extensions: Abstraction principles and the grounded extension. In Proceedings of the European Conferences on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'09), volume 5590 of Lecture Notes in Computer Science, pages 107-118. Springer, 2009.
[7]	Martin Caminada. On the issue of reinstatement in argumentation. In Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA'06), pages 111-123. Springer, 2006.
[8]	Claudette Cayrol, Florence Dupin de Saint-Cyr, and Marie-Christine Lagasquie-Schiex. Change in abstract argumentation frameworks: Adding an argument. Journal of Artificial Intelligence Research, 38:49-84, 2010.
[9]	Sylvie Coste-Marquis, Sébastien Konieczny, Jean-Guy Mailly, and Pierre Marquis. On the Revision of Argumentation Systems: Minimal Change of Arguments Statuses. In Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR'14), 2014, to appear.
[10]	Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming, and n-person games. Artificial Intelligence, 77(2):321-357, 1995.
[11]	Peter Gärdenfors. Knowledge In Flux. Cambridge University Press, Cambridge, UK, 1988.
[12]	Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52:263-294, 1991.
[13]	Dionysios Kontarinis, Elise Bonzon, Nicolas Maudet, Alan Perotti, Leon van der Torre, and Serena Villata. Rewriting rules for the computation of goal-oriented changes in an argumentation system. In 14th International Workshop on Computational Logic in Multi-Agent Systems (CLIMA XIV), 2013.
[14]	Daniel Le Berre, and Anne Parrain. The Sat4j library, release 2.2. In Journal on Satisfiability, Boolean Modeling and Computation, Volume 7, 2010. pages 59-64.