Paper Info
Title
LTL Fragments are Hard for Standard Parameterisations.
Abstract
We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth. We show that all operator fragments of LTL under the investigated parameterisations are intractable in the sense of parameterised complexity.
Year
DOI
Venue
2015
10.1109/TIME.2015.9
Workshops
Keywords
Field
DocType
LTL fragments,LTL satisfiability,model checking problems,parameterisations,parameterised complexity,linear temporal logic
Discrete mathematics,Model checking,Satisfiability,Algorithm,Linear temporal logic,Turing machine,Operator (computer programming),Treewidth,Pathwidth,Mathematics,Propositional variable
Journal
Volume
ISSN
Citations 
abs/1504.06187
1530-1311
1
PageRank 
References 
Authors
0.36
8
2
Name
Order
Citations
PageRank
Martin Lück110.36
Arne Meier221.08