Complexity of modal logics with Presburger constraints
We introduce the Extended Modal Logic EML with regularity constraints and full Presburger constraints on the number of children that generalize graded modalities, also known as number restrictions in description logics. We show that EML satisfiability is only PSPACE-complete by designing a Ladner-like algorithm. This extends a well-known and nontrivial PSPACE upper bound for graded modal logic. Furthermore, we provide a detailed comparison with logics that contain Presburger constraints and that are dedicated to query XML documents. As an application, we provide a logarithmic space reduction from a variant of Sheaves Logic SL into EML that allows us to establish that its satisfiability problem is also PSPACE-complete, significantly improving the best known upper bound. (C) 2010 Elsevier B.V. All rights reserved.
modal logic regularity constraint ladner-like algorithm arithmetical constraint computational complexity