Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4663034 | Journal of Applied Logic | 2010 | 13 Pages |
Abstract
In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss,