Strong Backdoors for Default Logic

verfasst von

Johannes Klaus Fichte, Arne Meier, Irena Schindler

Abstract

In this article, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor) for various kinds of target classes (CNF, KROM, MONOTONE) and all SCHAEFER classes. Also, we study generalisations of HORN-formulas, namely QHORN, RHORN, as well as DUALHORN. For these classes, we also classify the computational complexity of the implication problem. We show that backdoor detection is fixed-parameter tractable for the considered target classes and prove a complete trichotomy for backdoor evaluation. The problems are either fixed-parameter tractable, para-DeltaP2-complete, or para-NP-complete, depending on the target class.

Organisationseinheit(en)

Institut für Theoretische Informatik

Externe Organisation(en)

Linkoping University

Typ

Artikel

Journal

ACM Transactions on Computational Logic

Band

25

Anzahl der Seiten

36

ISSN

1529-3785

Publikationsdatum

17.06.2024

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Theoretische Informatik, Allgemeine Computerwissenschaft, Logik, Computational Mathematics

Elektronische Version(en)

https://doi.org/10.1145/3655024 (Zugang: Offen)