LTL Fragments are Hard for Standard Parameterisations
classification
💻 cs.LO
cs.CC
keywords
parameterisationscomplexityfragmentsinvestigatedstandardcheckingclassifydepth
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.