Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 15 |
| Seitenumfang | 36 |
| Fachzeitschrift | ACM Transactions on Computational Logic |
| Jahrgang | 25 |
| Ausgabenummer | 3 |
| Frühes Online-Datum | 30 März 2024 |
| Publikationsstatus | Verö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
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
- Mathematik (insg.)
- Logik
- Mathematik (insg.)
- Computational Mathematics
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: ACM Transactions on Computational Logic, Jahrgang 25, Nr. 3, 15, 17.06.2024.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
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 -