Matching entries: 0
settings...
AuthorTitleYearJournal/ProceedingsReftypeDOI/URL
Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Pührer, J., Redl, C., Ricca, F., Schneider, P., Schwengerer, M., Spendier, L.K., Wallner, J.P. and Xiao, G. The Fourth Answer Set Programming Competition: Preliminary Report 2013 Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013, pp. 42-53  inproceedings DOI  
Abstract: Answer Set Programming is a well-established paradigm of declarative programming in close relationship with other declarative formalisms such as SAT Modulo Theories, Constraint Handling Rules, PDDL and many others. Since its first informal editions, ASP systems are compared in the nowadays customary ASP Competition. The fourth ASP Competition, held in 2012/2013, is the sequel to previous editions and it was jointly organized by University of Calabria (Italy) and the Vienna University of Technology (Austria). Participants competed on a selected collection of benchmark problems, taken from a variety of research areas and real world applications. The Competition featured two tracks: the Model and Solve Track, held on an open problem encoding, on an open language basis, and open to any kind of system based on a declarative specification paradigm; and the System Track, held on the basis of fixed, public problem encodings, written in a standard ASP language.
BibTeX:
@inproceedings{Alvianoetal2013,
  author = {Mario Alviano and Francesco Calimeri and G\"unther Charwat and Minh Dao-Tran and Carmine Dodaro and Giovambattista Ianni and Thomas Krennwallner and Martin Kronegger and Johannes Oetsch and Andreas Pfandler and J\"org P\"uhrer and Christoph Redl and Francesco Ricca and Patrik Schneider and Martin Schwengerer and Lara K. Spendier and Johannes P. Wallner and Guohui Xiao},
  title = {The Fourth Answer Set Programming Competition: Preliminary Report},
  booktitle = {Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013},
  editor = {Pedro Cabalar and Tran Cao Son},
  publisher = {Springer},
  year = {2013},
  volume = {8148},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {42--53},
  doi = {10.1007/978-3-642-40564-8_5}
}
Ambroz, T., Charwat, G., Jusits, A., Wallner, J.P. and Woltran, S. ARVis: Visualizing Relations between Answer Sets 2013 Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013, pp. 73-78  inproceedings DOI  
Abstract: Answer set programming (ASP) is nowadays one of the most popular modeling languages in the areas of Knowledge Representation and Artificial Intelligence. Hereby one represents the problem at hand in such a way that each model of the ASP program corresponds to one solution of the original problem. In recent years, several tools which support the user in developing ASP applications have been introduced. However, explicit treatment of one of the main aspects of ASP, multiple solutions, has received less attention within these tools. In this work, we present a novel system to visualize relations between answer sets of a given program. The core idea of the system is that the user specifies the concept of a relation by an ASP program itself. This yields a highly flexible system that suggests potential applications beyond development environments, e.g., applications in the field of abduction, which we will discuss in a case study.
BibTeX:
@inproceedings{AmbrozCJWW2013,
  author = {Thomas Ambroz and G\"unther Charwat and Andreas Jusits and Johannes P. Wallner and Stefan Woltran},
  title = {{ARVis}: Visualizing Relations between Answer Sets},
  booktitle = {Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013},
  editor = {Pedro Cabalar and Tran Cao Son},
  publisher = {Springer},
  year = {2013},
  volume = {8148},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {73--78},
  doi = {10.1007/978-3-642-40564-8_8}
}
Brewka, G., Ellmauthaler, S., Strass, H., Wallner, J.P. and Woltran, S. Abstract Dialectical Frameworks Revisited 2013 Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, pp. 803-809  inproceedings URL 
Abstract: We present various new concepts and results related to abstract dialectical frameworks (ADFs), a powerful generalization of Dung's argumentation frameworks (AFs). In particular, we show how the existing definitions of stable and preferred semantics which are restricted to the subcase of so-called bipolar ADFs can be improved and generalized to arbitrary frameworks. Furthermore, we introduce preference handling methods for ADFs, allowing for both reasoning with and about preferences. Finally, we present an implementation based on an encoding in answer set programming.
BibTeX:
@inproceedings{BrewkaESWW2013,
  author = {Gerhard Brewka and Stefan Ellmauthaler and Hannes Strass and Johannes P. Wallner and Stefan Woltran},
  title = {Abstract Dialectical Frameworks Revisited},
  booktitle = {Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013},
  editor = {Francesca Rossi},
  publisher = {AAAI Press / IJCAI},
  year = {2013},
  pages = {803--809},
  url = {http://ijcai.org/Proceedings/13/Papers/125.pdf}
}
Brochenin, Ré., Linsbichler, T., Maratea, M., Wallner, J.P. and Woltran, S. Abstract solvers for Dung's argumentation frameworks 2015 Proceedings of the Third Workshop on Theory and Applications of Formal Argumentation, TAFA 2015, Revised Selected Papers, pp. 40-58  inproceedings DOI  
Abstract: Abstract solvers are a quite recent method to uniformly describe algorithms in a rigorous formal way and have proven successful in declarative paradigms such as Propositional Satisfiability and Answer-Set Programming. In this paper, we apply this machinery for the first time to a dedicated AI formalism, namely Dung's abstract argumentation frameworks. We provide descriptions of several advanced algorithms for the preferred semantics in terms of abstract solvers, and moreover, show how slight adaptions thereof directly lead to new algorithms.
BibTeX:
@inproceedings{BrocheninLMWW2015,
  author = {R{\'{e}}mi Brochenin and Thomas Linsbichler and Marco Maratea and Johannes P. Wallner and Stefan Woltran},
  title = {Abstract solvers for Dung's argumentation frameworks},
  booktitle = {Proceedings of the Third Workshop on Theory and Applications of Formal Argumentation, TAFA 2015, Revised Selected Papers},
  editor = {Elizabeth Black and Sanjay Modgil and Nir Oren},
  publisher = {Springer},
  year = {2015},
  volume = {9524},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {40--58},
  doi = {10.1007/978-3-319-28460-6_3}
}
Charwat, G., Dvořák, W., Gaggl, S.A., Wallner, J.P. and Woltran, S. Methods for Solving Reasoning Problems in Abstract Argumentation - A Survey 2015 Artificial Intelligence Vol. 220 , pp. 28-63  article DOI  
Abstract: Within the last decade, abstract argumentation has emerged as a central field in Artificial Intelligence. Besides serving as a core formalism for many advanced argumentation systems, abstract argumentation has also served to capture several nonmonotonic logics and other AI related principles. Although the idea of abstract argumentation is appealingly simple, several reasoning problems in this formalism exhibit high computational complexity. This calls for advanced techniques when it comes to implementation issues, a challenge which has been recently faced from different angles. In this survey, we give an overview on different methods for solving reasoning problems in abstract argumentation and compare their particular features. Moreover, we highlight available state-of-the-art systems for abstract argumentation, which put these methods to practice.
BibTeX:
@article{CharwatDGWW2015,
  author = {G\"unther Charwat and Dvo\v{r}\'{a}k, Wolfgang and Sarah A. Gaggl and Johannes P. Wallner and Woltran, Stefan},
  title = {Methods for Solving Reasoning Problems in Abstract Argumentation - A Survey},
  journal = {Artificial Intelligence},
  year = {2015},
  volume = {220},
  pages = {28--63},
  doi = {10.1016/j.artint.2014.11.008}
}
Charwat, G., Dvořák, W., Gaggl, S.A., Wallner, J.P. and Woltran, S. Implementing Abstract Argumentation - A Survey 2013 Technische Universität Wien (DBAI-TR-2013-82)  techreport URL 
Abstract: Within the last decade, abstract argumentation has emerged as a central field in Artificial Intelligence. Besides serving as a core formalism for many advanced argumentation systems, this is mainly due to the fact that abstract argumentation has been shown to capture several nonmonotonic logics and other AI related principles. Although the idea of abstract argumentation is appealingly simple, several reasoning problems in this formalism suffer from a high computational complexity. This calls for advanced techniques when it comes to implementation issues, a challenge which has been recently faced from different angles. In this survey, we give an overview on different methods for solving abstract argumentation problems and compare their particular features. Moreover, we give links to available state-of-the-art systems for abstract argumentation, which put these methods to practice.
BibTeX:
@techreport{DBAI-TR-2013-82,
  author = {G\"unther Charwat and Wolfgang Dvo\v{r}\'{a}k and Sarah A. Gaggl and Johannes P. Wallner and Stefan Woltran},
  title = {Implementing Abstract Argumentation - A Survey},
  institution = {Technische Universit\"at Wien},
  year = {2013},
  number = {DBAI-TR-2013-82},
  url = {http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2013-82.pdf}
}
Charwat, G., Ianni, G., Krennwallner, T., Kronegger, M., Pfandler, A., Redl, C., Schwengerer, M., Spendier, L.K., Wallner, J.P. and Xiao, G. VCWC: A Versioning Competition Workflow Compiler 2013 Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013, pp. 233-238  inproceedings DOI  
BibTeX:
@inproceedings{Charwatetal2013,
  author = {G\"unther Charwat and Giovambattista Ianni and Thomas Krennwallner and Martin Kronegger and Andreas Pfandler and Christoph Redl and Martin Schwengerer and Lara K. Spendier and Johannes P. Wallner and Guohui Xiao},
  title = {{VCWC}: A Versioning Competition Workflow Compiler},
  booktitle = {Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013},
  editor = {Pedro Cabalar and Tran Cao Son},
  publisher = {Springer},
  year = {2013},
  volume = {8148},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {233--238},
  doi = {10.1007/978-3-642-40564-8_23}
}
Charwat, G., Wallner, J.P. and Woltran, S. Utilizing ASP for Generating and Visualizing Argumentation Frameworks 2012 Proceedings of the Fifth Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2012, pp. 51-65  inproceedings URL 
Abstract: Within the area of computational models of argumentation, the instantiation-based approach is gaining more and more attention, not at least because meaningful input for Dung’s abstract frameworks is provided in that way. In a nutshell, the aim of instantiation-based argumentation is to form, from a given knowledge base, a set of arguments and to identify the conflicts between them. The resulting network is then evaluated by means of extension-based semantics on an abstract level, i.e. on the resulting graph. While several systems are nowadays available for the latter step, the automation of the instantiation process itself has received less attention. In this work, we provide a novel approach to construct and visualize an argumentation framework from a given knowledge base. The system we propose relies on Answer-Set Programming and follows a two-step approach. A first program yields the logic-based arguments as its answer-sets; a second program is then used to specify the relations between arguments based on the answer-sets of the first program. As it turns out, this approach not only allows for a flexible and extensible tool for instantiation-based argumentation, but also provides a new method for answer-set visualization in general.
BibTeX:
@inproceedings{CharwatWW2012,
  author = {Charwat, G\"unther and Johannes P. Wallner and Woltran, Stefan},
  title = {Utilizing ASP for Generating and Visualizing Argumentation Frameworks},
  booktitle = {Proceedings of the Fifth Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2012},
  editor = {Fink, Michael and Lierler, Yuliya},
  year = {2012},
  pages = {51--65},
  url = {https://sites.google.com/site/aspocp12/programme/charwat-etal.pdf}
}
Diller, M., Wallner, J.P. and Woltran, S. Reasoning in Abstract Dialectical Frameworks Using Quantified Boolean Formulas 2014 Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014, pp. 241-252  inproceedings DOI  
Abstract: Abstract dialectical frameworks (ADFs) constitute a recent and powerful generalization of Dung's argumentation frameworks (AFs), where the relationship between the arguments is specified via Boolean formulas. Recent results have shown that this enhancement comes with the price of higher complexity compared to AFs. In fact, acceptance problems in the world of ADFs can be hard even for the third level of the polynomial hierarchy. In order to implement reasoning problems on ADFs, systems for quantified Boolean formulas (QBFs) thus are suitable engines to be employed. In this paper we present QBF encodings on ADF problems generalizing recent work on QBFs for AF labellings. Our encodings not only provide a uniform and modular way of translating reasoning in ADFs to QBFs, but also build the basis for a novel system. We present a prototype implementation for the admissible and preferred semantics and evaluate its performance in comparison with another state-of-the-art tool for ADFs.
BibTeX:
@inproceedings{DillerWW2014,
  author = {Martin Diller and Johannes P. Wallner and Stefan Woltran},
  title = {Reasoning in Abstract Dialectical Frameworks Using Quantified {B}oolean Formulas},
  booktitle = {Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014},
  editor = {Simon Parsons and Nir Oren and Chris Reed and Federico Cerutti},
  publisher = {IOS Press},
  year = {2014},
  volume = {266},
  series = {Frontiers in Artificial Intelligence and Applications},
  pages = {241--252},
  doi = {10.3233/978-1-61499-436-7-241}
}
Diller, M., Wallner, J.P. and Woltran, S. Reasoning in Abstract Dialectical Frameworks Using Quantified Boolean Formulas 2015 Argument & Computation Vol. 6 (2), pp. 149-177  article DOI  
Abstract: Abstract dialectical frameworks (ADFs) constitute a recent and powerful generalization of Dung's argumentation frameworks (AFs), where the relationship between the arguments can be specified via Boolean formulas. Recent results have shown that this enhancement comes with the price of higher complexity compared to AFs. In fact, acceptance problems in the world of ADFs can be hard even for the third level of the polynomial hierarchy. In order to implement reasoning problems on ADFs, systems for quantified Boolean formulas (QBFs) thus are suitable engines to be employed. In this paper we give complexity sensitive QBF encodings of ADF problems generalizing recent work on QBFs for AF labellings. Our encodings provide a uniform and modular way of translating reasoning in ADFs to QBFs, that can be used as the basis for novel systems for ADF reasoning.
BibTeX:
@article{DillerWW2015,
  author = {Martin Diller and Johannes P. Wallner and Stefan Woltran},
  title = {Reasoning in Abstract Dialectical Frameworks Using Quantified {B}oolean Formulas},
  journal = {Argument \& Computation},
  year = {2015},
  volume = {6},
  number = {2},
  pages = {149--177},
  doi = {10.1080/19462166.2015.1036922}
}
Dvořák, W., Gaggl, S.A., Linsbichler, T. and Wallner, J.P. Reduction-based Approaches to Implement Modgil's Extended Argumentation Frameworks 2015 Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation. Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, pp. 249-264  incollection DOI  
Abstract: This paper reconsiders Modgil's Extended Argumentation Frameworks (EAFs) that extend Dung's abstract argumentation frameworks by attacks on attacks. This allows to encode preferences directly in the framework and thus also to reason about the preferences themselves. As a first step to reduction-based approaches to implement EAFs, we give an alternative (but equivalent) characterization of acceptance in EAFs. Then we use this characterization to provide EAF encodings for answer set programming and propositional logic. Moreover, we address an open complexity question and the expressiveness of EAFs.
BibTeX:
@incollection{DvorakGLW2015,
  author = {Wolfgang Dvo\v{r}\'{a}k and Sarah A. Gaggl and Thomas Linsbichler and Johannes P. Wallner},
  title = {Reduction-based Approaches to Implement {M}odgil's Extended Argumentation Frameworks},
  booktitle = {Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation. Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday},
  editor = {Thomas Eiter and Hannes Strass and Miros\l{}aw Truszczy{\'n}ski and Stefan Woltran},
  publisher = {Springer},
  year = {2015},
  volume = {9060},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {249--264},
  doi = {10.1007/978-3-319-14726-0_17}
}
Dvořák, W., Gaggl, S.A., Wallner, J.P. and Woltran, S. Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems 2011 Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011, pp. 117-130  inproceedings URL 
Abstract: Dung's famous abstract argumentation frameworks represent the core formalism for many problems and applications in the field of argumentation which significantly evolved within the last decade. Recent work in the field has thus focused on implementations for these frameworks, whereby one of the main approaches is to use Answer-Set Programming (ASP). While some of the argumentation semantics can be nicely expressed within the ASP language, others required rather cumbersome encoding techniques. Recent advances in ASP systems, in particular, the metasp optimization frontend for the ASP-package gringo/claspD provides direct commands to filter answer sets satisfying certain subset-minimality (or -maximality) constraints. This allows for much simpler encodings compared to the ones in standard ASP language. In this paper, we experimentally compare the original encodings (for the argumentation semantics based on preferred, semi-stable, and respectively, stage extensions) with new metasp encodings. Moreover, we provide novel encodings for the recently introduced resolution-based grounded semantics. Our experimental results indicate that the metasp approach works well in those cases where the complexity of the encoded problem is adequately mirrored within the metasp approach.
BibTeX:
@inproceedings{DvorakGWW2011,
  author = {Dvo\v{r}\'{a}k, Wolfgang and Sarah A. Gaggl and Johannes P. Wallner and Woltran, Stefan},
  title = {Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems},
  booktitle = {Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011},
  editor = {Salvador Abreu and Johannes Oetsch and J\"{o}rg P\"{u}hrer and Dietmar Seipel and Hans Tompits and Masanobu Umeda and Armin Wolf},
  year = {2011},
  pages = {117--130},
  url = {http://arxiv.org/abs/1108.4942}
}
Dvořák, W., Gaggl, S.A., Wallner, J.P. and Woltran, S. Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems 2013 Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011, Revised Selected Papers, pp. 114-133  inproceedings DOI  
Abstract: Dung’s famous abstract argumentation frameworks represent the core formalism for many problems and applications in the field of argumentation which significantly evolved within the last decade. Recent work in the field has thus focused on implementations for these frameworks, whereby one of the main approaches is to use Answer-Set Programming (ASP). While some of the argumentation semantics can be nicely expressed within the ASP language, others required rather cumbersome encoding techniques. Recent advances in ASP systems, in particular, the metasp optimization front-end for the ASP-package gringo/claspD provide direct commands to filter answer sets satisfying certain subset-minimality (or -maximality) constraints. This allows for much simpler encodings compared to the ones in standard ASP language. In this paper, we experimentally compare the original encodings (for the argumentation semantics based on preferred, semi-stable, and respectively, stage extensions) with new metasp encodings. Moreover, we provide novel encodings for the recently introduced resolution-based grounded semantics. Our experimental results indicate that the metasp approach works well in those cases where the complexity of the encoded problem is adequately mirrored within the metasp approach.
BibTeX:
@inproceedings{DvorakGWW2013,
  author = {Dvo\v{r}\'{a}k, Wolfgang and Sarah A. Gaggl and Johannes P. Wallner and Woltran, Stefan},
  title = {Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems},
  booktitle = {Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011, Revised Selected Papers},
  editor = {Hans Tompits and Salvador Abreu and Johannes Oetsch and J\"{o}rg P\"{u}hrer and Dietmar Seipel and Masanobu Umeda and Armin Wolf},
  publisher = {Springer},
  year = {2013},
  volume = {7773},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {114--133},
  doi = {10.1007/978-3-642-41524-1_7}
}
Dvořák, W., Gaggl, S.A., Wallner, J.P. and Woltran, S. Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems 2011 Technische Universität Wien (DBAI-TR-2011-70)  techreport URL 
Abstract: Dung’s famous abstract argumentation frameworks represent the core formalism for many problems and applications in the field of argumentation which significantly evolved within the last decade. Recent work in the field has thus focused on implementations for these frameworks, whereby one of the main approaches is to use Answer-Set Programming (ASP). While some of the argumentation semantics can be nicely expressed within the ASP language, others required rather cumbersome encoding techniques. Recent advances in ASP systems, in particular, the metasp optimization frontend for the ASP-package gringo/claspD provides direct commands to filter answer-sets satisfying certain subset-minimality (or -maximality) constraints. This allows for much simpler encodings compared to the ones in standard ASP language. In this paper, we experimentally compare the original encodings (for the argumentation semantics based on preferred, semi-stable, and respectively, stage extensions) with new metasp encodings, thus evaluating the efficiency of the novel metasp technique. Moreover, we provide novel encodings for the recently introduced resolution-based grounded semantics. Our experimental results indicate that the metasp approach works well in those cases where the complexity of the encoded problem is adequately mirrored within the metasp approach.
BibTeX:
@techreport{DBAI-TR-2011-70,
  author = {Wolfgang Dvo\v{r}\'{a}k and Sarah A. Gaggl and Johannes P. Wallner and Stefan Woltran},
  title = {Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems},
  institution = {Technische Universit\"at Wien},
  year = {2011},
  number = {DBAI-TR-2011-70},
  url = {http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2011-70.pdf}
}
Dvořák, W., Järvisalo, M., Wallner, J.P. and Woltran, S. Complexity-Sensitive Decision Procedures for Abstract Argumentation 2012 Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR 2012, pp. 54-64  inproceedings URL 
Abstract: Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the areas of Knowledge Representation and Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semistable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.
BibTeX:
@inproceedings{DvorakJWW2012a,
  author = {Dvo\v{r}\'{a}k, Wolfgang and J\"{a}rvisalo, Matti and Johannes P. Wallner and Woltran, Stefan},
  title = {Complexity-Sensitive Decision Procedures for Abstract Argumentation},
  booktitle = {Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR 2012},
  editor = {Brewka, Gerhard and Eiter, Thomas and McIlraith, Sheila A.},
  publisher = {AAAI Press},
  year = {2012},
  pages = {54--64},
  url = {http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4508}
}
Dvořák, W., Järvisalo, M., Wallner, J.P. and Woltran, S. Complexity-Sensitive Decision Procedures for Abstract Argumentation (Extended Abstract) 2015 Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, pp. 4173-4177  inproceedings URL 
BibTeX:
@inproceedings{DvorakJWW2015,
  author = {Dvo\v{r}\'{a}k, Wolfgang and J\"{a}rvisalo, Matti and Johannes P. Wallner and Woltran, Stefan},
  title = {Complexity-Sensitive Decision Procedures for Abstract Argumentation (Extended Abstract)},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015},
  editor = {Qiang Yang and Michael Wooldridge},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  year = {2015},
  pages = {4173--4177},
  url = {http://ijcai.org/Proceedings/15/Papers/590.pdf}
}
Dvořák, W., Järvisalo, M., Wallner, J.P. and Woltran, S. Complexity-Sensitive Decision Procedures for Abstract Argumentation 2014 Artificial Intelligence Vol. 206 , pp. 53-78  article DOI  
Abstract: Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the area of Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semi-stable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.
BibTeX:
@article{DvorakJWW2014,
  author = {Dvo\v{r}\'{a}k, Wolfgang and J\"{a}rvisalo, Matti and Johannes P. Wallner and Woltran, Stefan},
  title = {Complexity-Sensitive Decision Procedures for Abstract Argumentation},
  journal = {Artificial Intelligence},
  year = {2014},
  volume = {206},
  pages = {53--78},
  doi = {10.1016/j.artint.2013.10.001}
}
Dvořák, W., Järvisalo, M., Wallner, J.P. and Woltran, S. CEGARTIX: A SAT-Based Argumentation System 2012   unpublished URL 
BibTeX:
@unpublished{DvorakJWW2012b,
  author = {Dvo\v{r}\'{a}k, Wolfgang and J\"{a}rvisalo, Matti and Johannes P. Wallner and Woltran, Stefan},
  title = {{CEGARTIX}: A {SAT}-Based Argumentation System},
  year = {2012},
  note = {Presented at the Pragmatics of SAT Workshop (PoS 2012) \url{http://www.dbai.tuwien.ac.at/research/project/argumentation/papers/DvorakJWW2012PoS.pdf}},
  url = {http://www.dbai.tuwien.ac.at/research/project/argumentation/papers/DvorakJWW2012PoS.pdf}
}
Ellmauthaler, S. and Wallner, J.P. Evaluating Abstract Dialectical Frameworks with ASP 2012 Proceedings of the Fourth International Conference on Computational Models of Argument, COMMA 2012, pp. 505-506  inproceedings DOI  
BibTeX:
@inproceedings{EllmauthalerW2012,
  author = {Ellmauthaler, Stefan and Johannes P. Wallner},
  title = {Evaluating Abstract Dialectical Frameworks with {ASP}},
  booktitle = {Proceedings of the Fourth International Conference on Computational Models of Argument, COMMA 2012},
  editor = {Verheij, Bart and Szeider, Stefan and Woltran, Stefan},
  publisher = {IOS Press},
  year = {2012},
  volume = {245},
  series = {Frontiers in Artificial Intelligence and Applications},
  pages = {505--506},
  doi = {10.3233/978-1-61499-111-3-505}
}
Gaggl, S.A., Manthey, N., Ronca, A., Wallner, J.P. and Woltran, S. Improved Answer-Set Programming Encodings for Abstract Argumentation 2015 Technische Universität Wien (DBAI-TR-2015-93)  techreport URL 
Abstract: The design of efficient solutions for abstract argumentation problems is a crucial step towards advanced argumentation systems. One of the most prominent approaches in the literature is to use Answer-Set Programming (ASP) for this endeavor. In this paper, we present new encodings for three prominent argumentation semantics using the concept of conditional literals in disjunctions as provided by the ASP-system clingo. Our new encodings are not only more succinct than previous versions, but also outperform them on standard benchmarks.
BibTeX:
@techreport{DBAI-TR-2015-93,
  author = {Sarah A. Gaggl and Norbert Manthey and Alessandro Ronca and Johannes P. Wallner and Stefan Woltran},
  title = {Improved Answer-Set Programming Encodings for Abstract Argumentation},
  institution = {Technische Universit\"at Wien},
  year = {2015},
  number = {DBAI-TR-2015-93},
  url = {http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2015-92.pdf}
}
Gaggl, S.A., Manthey, N., Ronca, A., Wallner, J.P. and Woltran, S. Improved answer-set programming encodings for abstract argumentation 2015 Theory and Practice of Logic Programming Vol. 15 (4-5), pp. 434-448  article DOI  
Abstract: The design of efficient solutions for abstract argumentation problems is a crucial step towards advanced argumentation systems. One of the most prominent approaches in the literature is to use Answer-Set Programming (ASP) for this endeavor. In this paper, we present new encodings for three prominent argumentation semantics using the concept of conditional literals in disjunctions as provided by the ASP-system clingo. Our new encodings are not only more succinct than previous versions, but also outperform them on standard benchmarks.
BibTeX:
@article{GagglMRWW2015,
  author = {Sarah A. Gaggl and Norbert Manthey and Alessandro Ronca and Johannes P. Wallner and Stefan Woltran},
  title = {Improved answer-set programming encodings for abstract argumentation},
  journal = {Theory and Practice of Logic Programming},
  year = {2015},
  volume = {15},
  number = {4--5},
  pages = {434--448},
  doi = {10.1017/S1471068415000149}
}
Mohacsi, S. and Wallner, J. A hybrid approach for model-based random testing 2010 Proceedings of the Second International Conference on Advances in System Testing and Validation Lifecycle, VALID 2010, pp. 10-15  inproceedings DOI  
Abstract: Random testing is a valuable supplement to systematic test methods because it discovers defects that are very hard to detect with systematic test strategies. We propose a novel approach for random test generation that combines the benefits of model-based testing, constraint satisfaction, and pure random testing. The proposed method has been incorporated into the IDATG (Integrating Design and Automated Test case Generation) tool-set and validated in a number of case studies. Their results indicate that using the new approach it is indeed possible to generate effective test cases in acceptable time.
BibTeX:
@inproceedings{MohacsiW2010,
  author = {Mohacsi, Stefan and Johannes Wallner},
  title = {A hybrid approach for model-based random testing},
  booktitle = {Proceedings of the Second International Conference on Advances in System Testing and Validation Lifecycle, VALID 2010},
  editor = {du Bousquet, Lydie and Per\"al\"a, Juho and Lorenz, Pascal},
  year = {2010},
  pages = {10--15},
  doi = {10.1109/VALID.2010.15}
}
Niskanen, A., Wallner, J.P. and Järvisalo, M. Optimal Status Enforcement in Abstract Argumentation 2016 Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 1216-1222  inproceedings URL 
Abstract: We present complexity results and algorithms for optimal status enforcement in abstract argumentation. Status enforcement is the task of adjusting a given argumentation framework (AF) to support given positive and negative argument statuses, i.e., to accept and reject specific arguments. We study optimal status enforcement as the problem of finding a structurally closest AF supporting given argument statuses. We establish complexity results for optimal status enforcement under several central AF semantics,develop constraint-based algorithms for NP and second-level completevariants of the problem, and empirically evaluate the procedures.
BibTeX:
@inproceedings{NiskanenWJ2016a,
  author = {Andreas Niskanen and Johannes P. Wallner and Matti J\"{a}rvisalo},
  title = {Optimal Status Enforcement in Abstract Argumentation},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016},
  editor = {Subbarao Kambhampati},
  publisher = {AAAI Press / IJCAI},
  year = {2016},
  pages = {1216--1222},
  url = {http://www.ijcai.org/Proceedings/16/Papers/176.pdf}
}
Niskanen, A., Wallner, J.P. and Järvisalo, M. Synthesizing Argumentation Frameworks from Examples 2016 Proceedings of the 22nd European Conference on Artificial Intelligence, ECAI 2016, pp. 551-559  inproceedings DOI  
Abstract: Argumentation is nowadays a core topic in AI research. Understanding computational and representational aspects of abstract argumentation frameworks (AFs) is a central topic in the study of argumentation. The study of realizability of AFs aims at understanding the expressive power of AFs under different semantics. We propose and study the AF synthesis problem as a natural extension of realizability, addressing some of the shortcomings arising from the relatively stringent definition of realizability. Specifically, AF synthesis seeks to construct, or synthesize, AFs that are semantically closest to the knowledge at hand even when no AFs exactly representing the knowledge exist. Going beyond defining the AF synthesis problem, we (i)~prove NP-completeness of AF synthesis under several semantics, (ii)~study basic properties of the problem in relation to realizability, (iii)~develop algorithmic solutions to AF synthesis using constrained optimization, (iv)~empirically evaluate our algorithms on different forms of AF synthesis instances, as well as (v)~discuss variants and generalization of AF synthesis.
BibTeX:
@inproceedings{NiskanenWJ2016b,
  author = {Andreas Niskanen and Johannes P. Wallner and Matti J\"{a}rvisalo},
  title = {Synthesizing Argumentation Frameworks from Examples},
  booktitle = {Proceedings of the 22nd European Conference on Artificial Intelligence, ECAI 2016},
  editor = {Gal A. Kaminka and Maria Fox and Paolo Bouquet and Eyke Hüllermeier and Virginia Dignum and Frank Dignum and Frank van Harmelen},
  publisher = {IOS Press},
  year = {2016},
  volume = {285},
  series = {Frontiers in Artificial Intelligence and Applications},
  pages = {551--559},
  doi = {10.3233/978-1-61499-672-9-551}
}
Niskanen, A., Wallner, J.P. and Järvisalo, M. Pakota: A System for Enforcement in Abstract Argumentation 2016 Proceedings of the 15th European Conference on Logics in Artificial Intelligence, JELIA 2016, pp. 385-400  inproceedings DOI  
Abstract: In this paper we describe Pakota, a system implementation that allows for solving enforcement problems over argumentation frameworks. Via harnessing Boolean satisfiability (SAT) and maximum satisfiability (MaxSAT) solvers, Pakota implements algorithms for extension and status enforcement under various central AF semantics, covering a range of NP-complete---via direct MaxSAT encodings---and Sigma^P_2-complete---via MaxSAT-based counterexample-guided abstraction refinement---enforcement problems. We overview the algorithmic approaches implemented in Pakota, and describe in detail the system architecture, features, interfaces, and usage of the system. Furthermore, we present an empirical evaluation on the impact of the choice of MaxSAT solvers on the scalability of the system, and also provide benchmark generators for extension and status enforcement.
BibTeX:
@inproceedings{NiskanenWJ2016c,
  author = {Andreas Niskanen and Johannes P. Wallner and Matti J\"{a}rvisalo},
  title = {Pakota: A System for Enforcement in Abstract Argumentation},
  booktitle = {Proceedings of the 15th European Conference on Logics in Artificial Intelligence, JELIA 2016},
  editor = {Loizos Michael and Antonis C. Kakas},
  publisher = {Springer},
  year = {2016},
  volume = {10021},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {385--400},
  doi = {10.1007/978-3-319-48758-8_25}
}
Pfandler, A., Rümmele, S., Wallner, J.P. and Woltran, S. On the Parameterized Complexity of Belief Revision 2015 Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, pp. 3149-3155  inproceedings URL 
Abstract: Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-theta^P_2, and FPT^NP[f(k)].
BibTeX:
@inproceedings{PfandlerRWW2015,
  author = {Andreas Pfandler and Stefan R\"ummele and Johannes P. Wallner and Stefan Woltran},
  title = {On the Parameterized Complexity of Belief Revision},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015},
  editor = {Qiang Yang and Michael Wooldridge},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  year = {2015},
  pages = {3149--3155},
  url = {http://ijcai.org/Proceedings/15/Papers/444.pdf}
}
Polberg, S., Wallner, J.P. and Woltran, S. Admissibility in the Abstract Dialectical Framework 2013 Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013, pp. 102-118  inproceedings DOI  
Abstract: The aim of this paper is to study the concept of admissibility in abstract dialectical frameworks (ADFs). While admissibility is well-understood in Dung-style frameworks, a generalization to ADFs is not trivial. Indeed, the original proposal turned out to behave unintuitively at certain instances. A recent approach circumvented this problem by using a three-valued concept. In this paper, we propose a novel two-valued approach which more directly follows the original understanding of admissibility. We compare the two approaches and show that they behave differently on certain ADFs. Our results imply that for generalizations of Dung-style frameworks, establishing a precise correspondence between two-valued (i.e. extension-based) and three-value (i.e. labeling-based) characterizations of argumentation semantics is not easy and requires further investigations.
BibTeX:
@inproceedings{PolbergWW2013,
  author = {Sylwia Polberg and Johannes P. Wallner and Stefan Woltran},
  title = {Admissibility in the Abstract Dialectical Framework},
  booktitle = {Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013},
  editor = {Jo{\~{a}}o Leite and Tran Cao Son and Paolo Torroni and Leon van der Torre and Stefan Woltran},
  publisher = {Springer},
  year = {2013},
  volume = {8143},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {102--118},
  doi = {10.1007/978-3-642-40624-9_7}
}
Polleres, A. and Wallner, J.P. On the relation between SPARQL1.1 and Answer Set Programming 2013 Technische Universität Wien (DBAI-TR-2013-84)  techreport URL 
Abstract: In the context of the emerging Semantic Web and the quest for a common logical framework underpinning its architecture, the relation of rule-based languages such as Answer Set Programming (ASP) and ontology languages such as the Web Ontology Language (OWL) has attracted a lot of attention in the literature over the past years. With its roots in Deductive Databases and Datalog though, ASP shares much more commonality with another Semantic Web standard, namely the Simple Protocol and RDF Query Language (SPARQL). In this paper, we take the recent approval of the SPARQL1.1 standard by the World Wide Web consortium (W3C) as an opportunity to introduce this standard to the Logic Programming community by providing a translation of SPARQL1.1 into ASP. In this translation, we explain and highlight peculiarities of the new W3C standard. Along the way, we survey existing literature on foundations of SPARQL and SPARQL1.1, and also combinations of SPARQL with ontology and rules languages. Thereby, apart from providing the means to implement and support SPARQL natively within Logic Programming engines and particularly ASP engines, we hope to pave the way for further research on a common logical framework for Semantic Web languages, including query languages, from an ASP point of view.
BibTeX:
@techreport{DBAI-TR-2013-84,
  author = {Axel Polleres and Johannes P. Wallner},
  title = {On the relation between {SPARQL1.1} and Answer Set Programming},
  institution = {Technische Universit\"at Wien},
  year = {2013},
  number = {DBAI-TR-2013-84},
  url = {http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2013-84.pdf}
}
Polleres, A. and Wallner, J.P. On the relation between SPARQL1.1 and Answer Set Programming 2013 Journal of Applied Non-Classical Logics Vol. 23 (1-2), pp. 159-212  article DOI  
Abstract: In the context of the emerging Semantic Web and the quest for a common logical framework underpinning its architecture, the relation of rule-based languages such as Answer Set Programming (ASP) and ontology languages such as the Web Ontology Language (OWL) has attracted a lot of attention in the literature over the past years. With its roots in Deductive Databases and Datalog though, ASP shares much more commonality with another Semantic Web standard, namely the Simple Protocol and RDF Query Language (SPARQL). In this paper, we take the recent approval of the SPARQL1.1 standard by the World Wide Web consortium (W3C) as an opportunity to introduce this standard to the Logic Programming community by providing a translation of SPARQL1.1 into ASP. In this translation, we explain and highlight peculiarities of the new W3C standard. Along the way, we survey existing literature on foundations of SPARQL and SPARQL1.1, and also combinations of SPARQL with ontology and rules languages. Thereby, apart from providing the means to implement and support SPARQL natively within Logic Programming engines and particularly ASP engines, we hope to pave the way for further research on a common logical framework for Semantic Web languages, including query languages, from an ASP point of view.
BibTeX:
@article{PolleresW2013,
  author = {Axel Polleres and Johannes P. Wallner},
  title = {On the relation between {SPARQL1.1} and Answer Set Programming},
  journal = {Journal of Applied Non-Classical Logics},
  year = {2013},
  volume = {23},
  number = {1--2},
  pages = {159--212},
  doi = {10.1080/11663081.2013.798992}
}
Saikko, P., Wallner, J.P. and Järvisalo, M. Implicit Hitting Set Algorithms for Reasoning Beyond NP 2016 Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016, pp. 104-113  inproceedings URL 
Abstract: Lifting a recent proposal by Moreno-Centeno and Karp, we propose a general framework for so-called implicit hitting set algorithms for reasoning beyond NP. The framework is motivated by empirically successful specific instantiations of the approach---based on interactions between a Boolean satisfiability (SAT) solver and an integer programming (IP) solver---in the context of maximum satisfiability (MaxSAT). The framework opens up opportunities for developing implicit hitting set algorithms for various important reasoning problems in KR by implementing domain-specific reasoning modules with SAT and IP solvers. We detail instantiations of the framework for the minimum satisfiability problem---as a natural dual of MaxSAT---and, as a central KR problem, for propositional abduction, covering the second level of the polynomial hierarchy. We show empirically that an implementation of the instantiation for propositional abduction surpasses the efficiency of an approach based on encoding and solving propositional abduction instances as disjunctive logic programming under answer set semantics. We also study key properties of the general framework.
BibTeX:
@inproceedings{SaikkoWJ2016,
  author = {Paul Saikko and Johannes P. Wallner and Matti J\"{a}rvisalo},
  title = {Implicit Hitting Set Algorithms for Reasoning Beyond {NP}},
  booktitle = {Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016},
  editor = {Chitta Baral and Jim Delgrande and Frank Wolter},
  publisher = {{AAAI} Press},
  year = {2016},
  pages = {104--113},
  url = {http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12812}
}
Strass, H. and Wallner, J.P. Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory 2014 Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning, KR 2014, pp. 101-110  inproceedings URL 
Abstract: Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung's abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and Truszczyński, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.
BibTeX:
@inproceedings{StrassW2014,
  author = {Hannes Strass and Johannes P. Wallner},
  title = {Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory},
  booktitle = {Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning, KR 2014},
  editor = {Chitta Baral and Giuseppe De Giacomo and Thomas Eiter},
  publisher = {AAAI Press},
  year = {2014},
  pages = {101--110},
  url = {http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/7917}
}
Strass, H. and Wallner, J.P. Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory 2015 Artificial Intelligence Vol. 226 , pp. 34-74  article DOI  
Abstract: Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the area of Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semi-stable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.
BibTeX:
@article{StrassW2015,
  author = {Hannes Strass and Johannes P. Wallner},
  title = {{Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory}},
  journal = {Artificial Intelligence},
  year = {2015},
  volume = {226},
  pages = {34--74},
  doi = {10.1016/j.artint.2015.05.003}
}
Strass, H. and Wallner, J.P. Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory 2013 Computer Science Institute, Leipzig University (2)  techreport DOI  
Abstract: Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung's abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and Truszczyński, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.
BibTeX:
@techreport{StrassW2013,
  author = {Hannes Strass and Johannes P. Wallner},
  title = {Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory},
  institution = {Computer Science Institute, Leipzig University},
  year = {2013},
  number = {2},
  doi = {http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-129614}
}
Thimm, M. and Wallner, J.P. Some Complexity Results on Inconsistency Measurement 2016 Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016, pp. 114-124  inproceedings URL 
Abstract: We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into three classes related to their complexity. The first class contains measures whose complexity are located on the first level of the polynomial hierarchy, the second class contains measures on the second level of the polynomial hierarchy, and the third class is located beyond the second level of the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them.
BibTeX:
@inproceedings{ThimmW2016,
  author = {Matthias Thimm and Johannes P. Wallner},
  title = {Some Complexity Results on Inconsistency Measurement},
  booktitle = {Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016},
  editor = {Chitta Baral and Jim Delgrande and Frank Wolter},
  publisher = {{AAAI} Press},
  year = {2016},
  pages = {114--124},
  url = {http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12810}
}
Wallner, J.P. Complexity Results and Algorithms for Argumentation - Dung's Frameworks and Beyond 2014 School: Vienna University of Technology, Institute of Information Systems  phdthesis URL 
Abstract: In the last couple of decades argumentation emerged as an important topic in Artificial Intelligence (AI). Having its origin in philosophy, law and formal logic, argumentation in combination with computer science has developed into various formal models, which nowadays are found in diverse applications including legal reasoning, E-Democracy tools, medical applications and many more. An integral part of many formal argumentation theories within AI is a certain notion of abstraction. Hereby the actual contents of arguments are disregarded, but only the relation between them is used for reasoning purposes. One very influential formal model for representing discourses abstractly are Dung's argumentation frameworks (AFs). AFs can simply be represented as directed graphs. The vertices correspond to abstract arguments and directed edges are interpreted as an attack relation for countering arguments. Many variants and generalizations of AFs have been devised, with abstract dialectical frameworks (ADFs) among the most general ones. ADFs are even more abstract than AFs: the relation between arguments is not fixed to the concept attack, but is specified via so-called acceptance conditions, describing the relationship via Boolean functions. The main computational challenge for AFs and ADFs is to compute jointly acceptable sets of arguments. Several criteria, termed semantics, have been proposed for accepting arguments. Applications of AFs or ADFs unfortunately face the harsh reality that almost all reasoning tasks defined for the frameworks are intractable. Decision problems for AFs can even be hard for the second level of the polynomial hierarchy. ADFs generalize AFs and thus are at least as computationally complex, but exact complexity bounds of many ADF problems are lacking in the literature. There have been some proposals how to implement reasoning tasks on AFs. Roughly these can be classified into reduction and direct approaches. The former approach solves the problem at hand by translation to another one, for which sophisticated solvers exist. However, at the start of this thesis, reduction approaches for argumentation were purely monolithic. Monolithic reduction approaches result into a single encoding and hardly incorporate domain-specific optimizations for more efficient computation. Direct approaches exploit structural or semantical properties of AFs for efficiency but must typically devise and implement an algorithm from scratch, including the highly consuming task of engineering solutions on a very deep algorithmic level e.g. the development of suitable data structures. In this thesis we provide three major contributions to the state of the art in abstract argumentation. First, we develop a novel hybrid approach that combines strengths of reduction and direct approaches. Our method reduces the problem at hand to iterative satisfiability (SAT) solving, i.e. a sequence of calls to a SAT-solver. Due to hardness for the second level of the polynomial hierarchy, we cannot avoid exponentially many SAT calls in the worst case. However, by exploiting inherent parameters of AFs, we provide a bound on the number of calls. Utilizing modern SAT technology to an even greater extent, we also employ more expressive variants of the SAT problem. It turns out that minimal correction sets (MCSes) and backbones of Boolean formulae are very well suited for our tasks. Like the iterative SAT algorithms, our algorithms based upon MCSes and backbones are hybrid approaches as well. Yet they are closer to monolithic reduction approaches and offer the benefit of requiring even less engineering effort and providing more declarativeness. Our second major contribution is to generalize our algorithms to ADFs. For doing so we first considerably extend ADF theory and provide a thorough complexity analysis for ADFs. Our results show that the reasoning tasks for ADFs are one step up in the polynomial hierarchy compared to their counterparts on AFs. Even though problems on ADFs suffer from hardness up to the third level of the polynomial hierarchy, our analysis shows that bipolar ADFs (BADFs) are not affected by this complexity jump. BADFs restrict the relations between arguments to be either of an attacking or supporting nature, but still offer a variety of interesting relations. Finally our third contribution is an empirical evaluation of implementations of our algorithms. Our novel algorithms outperform existing state-of-the-art systems for abstract argumentation. These results show that our hybrid approaches are indeed promising and that the provided proof-of-concept implementations can pave the way for applications for handling problems of increasing size and complexity.
BibTeX:
@phdthesis{Wallner2014,
  author = {Johannes P. Wallner},
  title = {Complexity Results and Algorithms for Argumentation - {D}ung's Frameworks and Beyond},
  school = {Vienna University of Technology, Institute of Information Systems},
  year = {2014},
  url = {http://permalink.obvsg.at/AC11706119}
}
Wallner, J.P., Niskanen, A. and Järvisalo, M. Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation 2016 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI 2016  inproceedings URL 
Abstract: Understanding the dynamics of argumentation frameworks (AFs) is important in the study of argumentation in AI. In this work, we focus on the so-called extension enforcement problem in abstract argumentation. We provide a nearly complete computational complexity map of fixed-argument extension enforcement under various major AF semantics, with results ranging from polynomial-time algorithms to completeness for the second-level of the polynomial hierarchy. Complementing the complexity results, we propose algorithms for NP-hard extension enforcement based on constrained optimization. Going beyond NP, we propose novel counterexample-guided abstraction refinement procedures for the second-level complete problems and present empirical results on a prototype system constituting the first approach to extension enforcement in its generality.
BibTeX:
@inproceedings{WallnerNJ2016,
  author = {Johannes P. Wallner and Andreas Niskanen and Matti J\"{a}rvisalo},
  title = {Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation},
  booktitle = {Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI 2016},
  editor = {Dale Schuurmans and Michael Wellman},
  year = {2016},
  note = {Accepted},
  url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12228}
}
Wallner, J.P., Weissenbacher, G. and Woltran, S. Advanced SAT Techniques for Abstract Argumentation 2013 Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013, pp. 138-154  inproceedings DOI  
Abstract: In the area of propositional satisfiability (SAT), tremendous progress has been made in the last decade. Today’s SAT technology covers not only the standard SAT problem, but also extensions thereof, such as computing a backbone (the literals which are true in all satisfying assignments) or minimal corrections sets (minimal subsets of clauses which if dropped leave an originally unsatisfiable formula satisfiable). In this work, we show how these methods can be applied to solve important problems from the area of abstract argumentation. In particular, we present new systems for semi-stable, ideal, and eager semantics. Our experimental results demonstrate the feasibility of this approach.
BibTeX:
@inproceedings{WallnerWW2013,
  author = {Johannes P. Wallner and Georg Weissenbacher and Stefan Woltran},
  title = {Advanced {SAT} Techniques for Abstract Argumentation},
  booktitle = {Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013},
  editor = {Jo{\~{a}}o Leite and Tran Cao Son and Paolo Torroni and Leon van der Torre and Stefan Woltran},
  publisher = {Springer},
  year = {2013},
  volume = {8143},
  series = {Lecture Notes in Artificial Intelligence},
  pages = {138--154},
  doi = {10.1007/978-3-642-40624-9_9}
}