Show simple item record

dc.identifier.uri Meier, Arne Ordyniak, Sebastian Sridharan, Ramanujan Schindler, Irena 2017-04-05T12:01:26Z 2017-04-05T12:01:26Z 2017
dc.identifier.citation Meier, A.; Ordyniak, S.; Sridharan, R.; Schindler, I.: Backdoors for linear temporal logic. In: Leibniz International Proceedings in Informatics, LIPIcs 63 (2017), 23. DOI:
dc.description.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. eng
dc.description.sponsorship DFG/ME 4279/1-1
dc.language.iso eng
dc.publisher Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
dc.relation.ispartofseries Leibniz International Proceedings in Informatics, LIPIcs 63 (2017)
dc.rights CC BY 3.0 Unported
dc.subject Backdoor sets eng
dc.subject Linear temporal logic eng
dc.subject Parameterized complexity eng
dc.subject Computer circuits eng
dc.subject Formal logic eng
dc.subject Parameterization eng
dc.subject Temporal logic eng
dc.subject Backdoor detections eng
dc.subject Backdoors eng
dc.subject Horn formulas eng
dc.subject Linear temporal logic eng
dc.subject Parameterized eng
dc.subject Parameterized complexity eng
dc.subject Satisfiability problems eng
dc.subject Parameter estimation eng
dc.subject.classification Konferenzschrift ger
dc.subject.ddc 004 | Informatik ger
dc.title Backdoors for linear temporal logic eng
dc.type Article
dc.type Text
dc.relation.issn 1868-8969
dc.bibliographicCitation.volume 63
dc.bibliographicCitation.firstPage 23
dc.description.version publishedVersion
tib.accessRights frei zug�nglich

Files in this item

This item appears in the following Collection(s):

Show simple item record


Search the repository


My Account

Usage Statistics