@misc{FichteTruszczynskiWoltran2015,
  author    = {Fichte, Johannes Klaus and Truszczynski, Miroslaw and Woltran, Stefan},
  title     = {Dual-normal logic programs},
  series = {Postprints der Universit{\"a}t Potsdam : Mathematisch-Naturwissenschaftliche Reihe},
  journal   = {Postprints der Universit{\"a}t Potsdam : Mathematisch-Naturwissenschaftliche Reihe},
  number    = {585},
  issn      = {1866-8372},
  doi       = {10.25932/publishup-41449},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-414490},
  pages     = {16},
  year      = {2015},
  abstract  = {Disjunctive Answer Set Programming is a powerful declarative programming paradigm with complexity beyond NP. Identifying classes of programs for which the consistency problem is in NP is of interest from the theoretical standpoint and can potentially lead to improvements in the design of answer set programming solvers. One of such classes consists of dual-normal programs, where the number of positive body atoms in proper rules is at most one. Unlike other classes of programs, dual-normal programs have received little attention so far. In this paper we study this class. We relate dual-normal programs to propositional theories and to normal programs by presenting several inter-translations. With the translation from dual-normal to normal programs at hand, we introduce the novel class of body-cycle free programs, which are in many respects dual to head-cycle free programs. We establish the expressive power of dual-normal programs in terms of SE- and UE-models, and compare them to normal programs. We also discuss the complexity of deciding whether dual-normal programs are strongly and uniformly equivalent.},
  language  = {en}
}
@misc{FichteHecherMeier2019,
  author    = {Fichte, Johannes Klaus and Hecher, Markus and Meier, Arne},
  title     = {Counting Complexity for Reasoning in Abstract Argumentation},
  series = {The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence},
  journal   = {The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence},
  publisher = {AAAI Press},
  address   = {Palo Alto},
  isbn      = {978-1-57735-809-1},
  pages     = {2827 -- 2834},
  year      = {2019},
  abstract  = {In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.},
  language  = {en}
}
@article{FichteSzeider2015,
  author    = {Fichte, Johannes Klaus and Szeider, Stefan},
  title     = {Backdoors to tractable answer set programming},
  series = {Artificial intelligence},
  volume    = {220},
  journal   = {Artificial intelligence},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0004-3702},
  doi       = {10.1016/j.artint.2014.12.001},
  pages     = {64 -- 103},
  year      = {2015},
  abstract  = {Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable. In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.},
  language  = {en}
}