Strong Backdoors for Default Logic

Publikation: Beitrag in FachzeitschriftArtikelForschungPeer-Review

Autoren

Externe Organisationen

  • Linkoping University
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Aufsatznummer15
Seitenumfang36
FachzeitschriftACM Transactions on Computational Logic
Jahrgang25
Ausgabenummer3
Frühes Online-Datum30 März 2024
PublikationsstatusVeröffentlicht - 17 Juni 2024

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.

ASJC Scopus Sachgebiete

Zitieren

Strong Backdoors for Default Logic. / Fichte, Johannes Klaus; Meier, Arne; Schindler, Irena.
in: ACM Transactions on Computational Logic, Jahrgang 25, Nr. 3, 15, 17.06.2024.

Publikation: Beitrag in FachzeitschriftArtikelForschungPeer-Review

Fichte JK, Meier A, Schindler I. Strong Backdoors for Default Logic. ACM Transactions on Computational Logic. 2024 Jun 17;25(3):15. Epub 2024 Mär 30. doi: 10.1145/3655024
Fichte, Johannes Klaus ; Meier, Arne ; Schindler, Irena. / Strong Backdoors for Default Logic. in: ACM Transactions on Computational Logic. 2024 ; Jahrgang 25, Nr. 3.
Download
@article{ed183e6326a54351a8cdbafb0bdaf411,
title = "Strong Backdoors for Default Logic",
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.",
keywords = "backdoors, default logic, Parameterised complexity",
author = "Fichte, {Johannes Klaus} and Arne Meier and Irena Schindler",
note = "Publisher Copyright: {\textcopyright} 2024 Copyright held by the owner/author(s).",
year = "2024",
month = jun,
day = "17",
doi = "10.1145/3655024",
language = "English",
volume = "25",
journal = "ACM Transactions on Computational Logic",
issn = "1529-3785",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

Download

TY - JOUR

T1 - Strong Backdoors for Default Logic

AU - Fichte, Johannes Klaus

AU - Meier, Arne

AU - Schindler, Irena

N1 - Publisher Copyright: © 2024 Copyright held by the owner/author(s).

PY - 2024/6/17

Y1 - 2024/6/17

N2 - 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.

AB - 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.

KW - backdoors

KW - default logic

KW - Parameterised complexity

UR - http://www.scopus.com/inward/record.url?scp=85200594708&partnerID=8YFLogxK

U2 - 10.1145/3655024

DO - 10.1145/3655024

M3 - Article

AN - SCOPUS:85200594708

VL - 25

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

SN - 1529-3785

IS - 3

M1 - 15

ER -

Von denselben Autoren