Abstract: | |
In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Here we classify the operator fragments of globally-operators for past/future/always, and the combination of them. Detection is shown to be fixed-parameter tractable (FPT) whereas the complexity of evaluation behaves differently. We show that for Krom formulas the problem is paraNP-complete. For Horn formulas, the complexity is shown to be either fixed parameter tractable or paraNP-complete depending on the considered operator fragment.
|
|
License of this version: | CC BY 3.0 Unported - https://creativecommons.org/licenses/by/3.0/ |
Publication type: | Article |
Publishing status: | publishedVersion |
Publication date: | 2017 |
Keywords english: | Backdoor sets, Linear temporal logic, Parameterized complexity, Computer circuits, Formal logic, Parameterization, Temporal logic, Backdoor detections, Backdoors, Horn formulas, Linear temporal logic, Parameterized, Parameterized complexity, Satisfiability problems, Parameter estimation |
DDC: | 004 | Informatik |
Controlled keywords(GND): | Konferenzschrift |
Showing items related by title, author, creator and subject.