The complexity of satisfiability for fragments of hybrid logic—Part I

C. Areces, P. Blackburn, M. Marx, Hybrid logic is the bounded fragment of first-order logic, in: Proc. WOLLIC-99, 1999, pp. 35–50. Areces, 2000, The computational complexity of hybrid temporal logics, Logic Journal of the IGPL, 8, 653, 10.1093/jigpal/8.5.653 M. Bauland, E. Hemaspaandra, H. Schnoor, I. Schnoor, Generalized modal satisfiability, in: Proc. STACS, 2006, pp. 500–511. M. Bauland, M. Mundhenk, T. Schneider, H. Schnoor, I. Schnoor, H. Vollmer, The tractability of model checking for LTL: the good, the bad, and the ugly fragments, in: Proc. M4M-5, 2007, pp. 125–140. Bauland, 2009, The complexity of generalized satisfiability for linear temporal logic, Logical Methods in Computer Science, 18, 493 Blackburn, 2000, Representation, reasoning, and relational structures: a hybrid logic manifesto, Logic Journal of the IGPL, 8, 10.1093/jigpal/8.3.339 Blackburn, 1995, Hybrid languages, Journal of Logic, Language and Information, 4, 41, 10.1007/BF01049415 Böhler, 2003, Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory, ACM–SIGACT Newsletter, 34, 38 Bozzelli, 2008, Complexity and succinctness issues for linear-time hybrid logics, vol. 5293, 48 Donini, 1992, The complexity of existential quantification in concept languages, Artificial Intelligence, 53, 309, 10.1016/0004-3702(92)90076-A Etessami, 1997, Counting quantifiers, successor relations, and logarithmic space, Journal of Computer and System Sciences, 54, 400, 10.1006/jcss.1997.1485 M. Franceschet, M. de Rijke, B. Schlingloff, Hybrid logics on linear structures: Expressivity and complexity, in: Proc. 10th TIME, 2003, pp. 166–173. Goranko, 1996, Hierarchies of modal and temporal logics with reference pointers, Journal of Logic, Language and Information, 5, 1, 10.1007/BF00215625 Hemaspaandra, 2001, The complexity of poor man's logic, Journal of Logic and Computation, 11, 609, 10.1093/logcom/11.4.609 Ladner, 1977, The computational complexity of provability in systems of modal propositional logic, SIAM Journal on Computing, 6, 467, 10.1137/0206033 Lewis, 1979, Satisfiability problems for propositional calculi, Mathematical Systems Theory, 13, 45, 10.1007/BF01744287 Meier, 2009, The complexity of satisfiability for fragments of hybrid logic—Part I, vol. 5734, 587 A. Meier, M. Mundhenk, T. Schneider, M. Thomas, F. Weiss, The complexity of satisfiability for fragments of hybrid logic—Part II, in: Proc. of the International Workshop on Hybrid Logic and Applications, HyLo 2010, submitted for publication. Mundhenk, 2009, The complexity of hybrid logics over equivalence relations, Journal of Logic, Language and Information, 493, 10.1007/s10849-009-9089-6 M. Mundhenk, T. Schneider, T. Schwentick, V. Weber, Complexity of hybrid logics over transitive frames, Journal of Applied Logic, in this issue. Papadimitriou, 1994 Pippenger, 1997 Post, 1941, The two-valued iterative systems of mathematical logic, Annals of Mathematical Studies, 5, 1 Regan, 1997, Gap-languages and log-time complexity classes, Theoretical Computer Science, 188, 101, 10.1016/S0304-3975(96)00288-5 T.J. Schaefer, The complexity of satisfiability problems, in: Proc. STOC, 1978, pp. 216–226. T. Schneider, The complexity of hybrid logics over restricted classes of frames, Ph.D. thesis, Univ. of Jena, 2007. H. Schnoor, Algebraic techniques for satisfiability problems, Ph.D. thesis, Univ. of Hannover, 2007. Schwentick, 2007, Bounded-variable fragments of hybrid logics, vol. 4393, 561 ten Cate, 2005, On the complexity of hybrid logics with binders, vol. 3634, 339 Vollmer, 1999 Weber, 2009, Branching-time logics repeatedly referring to states, Journal of Logic, Language and Information, 18, 593, 10.1007/s10849-009-9093-x