Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces

AbstractWe continue our study of the complexity of MSO-definable local temporal logics over concurrent systems that can be described by Mazurkiewicz traces. In previous papers, we showed that the satisfiability problem for any such logic is in PSPACE (provided the dependence alphabet is fixed, Gastin and Kuske (2003) [10]) and remains in PSPACE for all classical local temporal logics even if the dependence alphabet is part of the input, Gastin and Kuske (2007) [8]. In this paper, we consider the uniform satisfiability problem for arbitrary MSO-definable local temporal logics. For this problem, we prove multi-exponential lower and upper bounds that depend on the number of alternations of set quantifiers present in the chosen MSO-modalities