dynPARTIX is a system for abstract argumentation which is based on tree decompositions and dynamic programming. It is developed within the project "New Methods for Analyzing, Comparing, and Solving Argumentation Problems".
dynPARTIX is a system for abstract argumentation which is based on decomposition and dynamic programming. This work is motivated by the theoretical results from [1].
It makes use of the graph-parameter tree-width, which measures the "tree-likeness" of a graph. More specifically, tree-width is defined via certain decompositions of graphs, so-called tree-decompositions. The theoretical results in [1, 3] describe algorithms how reasoning can be done in such a way that the performance mainly depends on the tree-width of the given AF, but the running times remain linear in the size of the AF. To put this approach to practice, we shall use the SHARP framework, a C++ environment which includes heuristic methods to obtain tree decompositions, provides an interface to run algorithms on decompositions, and offers further useful features, for instance for parsing the input.
We borrow the input file format from the ASPARTIX system. The parser will recognize the following lines:
Any other lines (e.g. comments) will be ignored. The order of the definitions does not matter. If arguments are just defined implicitly within the attack relations (e.g. the input file contains att(a,b). but not arg(b).), one will receive a warning message, but the calculation continues. If there is an isolated argument that does not appear within the attack relations, it will be ignored for the calculation, but one will receive a corresponding message again.
First of all, let us take a look on some common program calls:
./dynpartix -f testinputA -s admissible
./dynpartix -f testinputA -s preferred --count
./dynpartix -f testinputA --skept d
./dynpartix -f testinputA -n semi --count
The option -f denotes the input file. -s semantics stands for the selection of the desired semantics. The admissible semantics is the default selection. With the option --cred d, the program will check if credulous acceptance holds for the argument d. Accordingly, --skept d checks if skeptical acceptance holds. Another option is --count for calculating the number of admissible resp. preferred extensions. Finally, the default option --enum enumerates the determined solutions. Please note that the options enum, count, cred and skept cannot be used concurrently. -n semi denotes that a semi-normalized tree decomposition is used.
For summarizing and extending the mentioned program call options, we provide the complete usage message:
Usage: ./dynpartix [-v] [-b] [-t] [-d] [-r <seed>] [-f <file>] [-n <normalization>] [-s <semantics>] [--enum[=number] | --count | --cred <arg> | --skept <arg>] -v print version information -b print benchmark information -t perform only tree decomposition step -d print just comma separated data: 'filename; seed; time; result;' -r seed initialize random number generator with <seed>. -f file the file to read the AF from -n normalization the tree decomposition normalization type, one of {norm (default}, semi} -s semantics the semantics, one of {admissible (default), stable, complete, preferred} --enum[=number] prints an enumeration of all solutions (default) number binds the displayed enumerations (default: not bounded) --count prints the number of solutions --cred arg checks whether the argument is credulously accepted or not --skept arg checks whether the argument is skeptically accepted or not
Let us consider the following input file containing the definition of a argumentation framework:
%arguments arg(a). arg(b). arg(c). arg(d). arg(e). arg(f). arg(g). %attacks att(a,b). att(c,b). att(c,d). att(d,c). att(d,e). att(e,g). att(f,e). att(g,f).
With this input, the program will find the admissible sets: {{},{g,d},{g,d,a},{d},{d,a},{c},{c,a},{a}}.
The counting solution (--count) will return 8 and --cred a will return YES, as the argument a appears in the admissible set {g,d,a}.
If the algorithm for calculating the preferred extensions is selected, the program will return the solution {{g,d,a},{c,a}}. As can be seen easily, the printed extensions are the maximal admissible extensions, i.e. they have no admissible superset.
Here we provide different versions of dynPARTIX as well as some benchmark examples for download:
[6] |
dynPARTIX - A Dynamic Programming Reasoner for Abstract Argumentation. Wolfgang Dvořák, Michael Morak, Clemens Nopp and Stefan Woltran Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP 2011), revised selected papers, pages 259-268, 2013 [paper at Springer] |
[5] |
dynPARTIX 2.0 - Dynamic Programming Argumentation Reasoning Tool. (demonstration extended abstract) Günther Charwat and Wolfgang Dvořák COMMA 2012: 507-508 |
[4] |
Towards Fixed-Parameter Tractable Algorithms for Abstract Argumentation. Wolfgang Dvořák, Reinhard Pichler, and Stefan Woltran In Artificial Intelligence, 186 (1): 1-37 (2011) [paper at sciencedirect] |
[3] |
Tree-Decomposition based Algorithms for Abstract Argumentation Frameworks Günther Charwat. Master's Thesis, Technische Universität Wien, Stefan Woltran and Wolfgang Dvořák advisors, 2012. [.pdf, obv] |
[2] |
dynPARTIX - A Dynamic Programming Reasoner for Abstract Argumentation.
(system description) Wolfgang Dvořák, Michael Morak, Clemens Nopp and Stefan Woltran. In Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP 2011) [arXiv:1108.4804] |
[1] |
Towards Fixed-Parameter Tractable Algorithms for
Argumentation. Wolfgang Dvořák, Reinhard Pichler and Stefan Woltran. In Fangzhen Lin, Ulrike Sattler and Miroslaw Truszczynski, editors, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), Toronto, Ontario, Canada, May 9-13, 2010, pages 112-122, AAAI Press, 2010. [.pdf] |