Representing Abstract Dialectical Frameworks with Binary Decision Diagrams

Stefan Ellmauthaler, Sarah A. Gaggl, Dominik Rusovac, Johannes Peter Wallner

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Abstract

Abstract dialectical frameworks (ADFs) are a well-studied generalisation of the prominent argumentation frameworks due to Phan Minh Dung. In this paper we propose to use reduced ordered binary decision diagrams (roBDDs) as a suitable representation of the acceptance conditions of arguments within ADFs. We first show that computational complexity of reasoning on ADFs represented by roBDDs is milder than in the general case, with a drop of one level in the polynomial hierarchy. Furthermore, we present a framework to systematically define heuristics for search space exploitation, based on easily retrievable properties of roBDDs and the recently proposed approach of weighted faceted navigation for answer set programming. Finally, we present preliminary experiments of an implementation of our approach showing promise both when compared to state-of-the-art solvers and when developing heuristics for reasoning.
Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Proceedings
EditorsGeorg Gottlob, Daniela Inclezan, Marco Maratea
PublisherSpringer
Pages177-189
Number of pages13
Volume13416
ISBN (Print)9783031157066
DOIs
Publication statusPublished - 2022
Event16th International Conference on Logic Programming and Non-monotonic Reasoning: LPNMR 2022 - Genova, Italy
Duration: 5 Sept 20228 Sept 2022
https://sites.google.com/view/lpnmr2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13416 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Logic Programming and Non-monotonic Reasoning
Abbreviated titleLPNMR 2022
Country/TerritoryItaly
CityGenova
Period5/09/228/09/22
Internet address

Keywords

  • Abstract dialectical frameworks
  • Binary decision diagrams

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Representing Abstract Dialectical Frameworks with Binary Decision Diagrams'. Together they form a unique fingerprint.

Cite this