Complexity of hybrid logics over transitive frames

Afanasiev, 2005, PDL for ordered trees, Journal of Applied Non-Classical Logics, 15, 115, 10.3166/jancl.15.115-135 Areces, 1999, A road-map on complexity for hybrid logics, vol. 1683, 307 Areces, 2000, The computational complexity of hybrid temporal logics, Logic Journal of the IGPL, 8, 653, 10.1093/jigpal/8.5.653 Areces, 2001, Hybrid logics: Characterization, interpolation and complexity, Journal of Symbolic Logic, 66, 977, 10.2307/2695090 Baader, 1996, Cardinality restrictions on concepts, Artificial Intelligence, 88, 195, 10.1016/S0004-3702(96)00010-0 Blackburn, 2000, Representation, reasoning, and relational structures: a hybrid logic manifesto, Logic Journal of the IGPL, 8, 339, 10.1093/jigpal/8.3.339 Blackburn, 1995, Hybrid languages, Journal of Logic, Language and Information, 4, 251, 10.1007/BF01049415 Blackburn, 1998, What are hybrid languages?, vol. 1, 41 Blackburn, 1999, Hybrid languages and temporal logic, Logic Journal of the IGPL, 7, 27, 10.1093/jigpal/7.1.27 Blackburn, 2001, Modal Logic, vol. 53 Börger, 1997, The classical decision problem Buchheit, 1993, Decidable reasoning in terminological knowledge representation systems, Journal of Artificial Intelligence Research, 1, 109, 10.1613/jair.21 Anuj Dawar, Martin Otto, Modal characterisation theorems over special classes of frames, in: Proc. of the 20th LICS, IEEE Computer Society, 2005, pp. 21–30. Demri, 1995, Uniform and non uniform strategies for tableaux calculi for modal logics, Journal of Applied Non-Classical Logics, 5, 10.1080/11663081.1995.10510844 Donini, 2000, EXPTIME tableaux for ALC, Artificial Intelligence, 124, 87, 10.1016/S0004-3702(00)00070-9 Franceschet, 2006, Model checking hybrid logics (with an application to semistructured data), Journal of Applied Logic, 4, 279, 10.1016/j.jal.2005.06.010 Massimo Franceschet, Maarten de Rijke, Bernd-Holger Schlingloff, Hybrid logics on linear structures: Expressivity and complexity, in: Proc. of the 10th TIME, IEEE Computer Society, 2003, pp. 166–173. Harald Ganzinger, Christoph Meyer, Margus Veanes, The two-variable guarded fragment with transitive relations, in: Proc. of the 14th LICS, IEEE Computer Society, 1999, pp. 24–34. Goranko, 1996, Hierarchies of modal and temporal logics with reference pointers, Journal of Logic, Language and Information, 5, 1, 10.1007/BF00215625 Goré, 1999, Tableau methods for substructural logics Goré, 2007, EXPTIME tableaux with global caching for description logics with transitive roles, inverse roles and role hierarchies, vol. 4548, 133 Grädel, 1999, On the restraining power of guards, Journal of Symbolic Logic, 64, 1719, 10.2307/2586808 Erich Grädel, Igor Walukiewicz, Guarded fixed point logic, in: Proc. of the 14th LICS, IEEE Computer Society, 1999, pp. 45–54. Immerman, 2004, The boundary between decidability and undecidability for transitive-closure logics, vol. 3210, 160 Kieronski, 2002, EXPSPACE-complete variant of guarded fragment with transitivity, vol. 2285, 608 Kieronski, 2003, The two-variable guarded fragment with transitive guards is 2EXP-TIME-hard, vol. 2620, 299 Kracht, 1995, Syntactic codes and grammar refinement, Journal of Logic, Language and Information, 4, 41, 10.1007/BF01048404 Kracht, 1997, Inessential features, vol. 1328, 43 Ladner, 1977, The computational complexity of provability in systems of modal propositional logic, SIAM Journal on Computing, 6, 467, 10.1137/0206033 Lutz, 2005, Keys, nominals, and concrete domains, Journal of Artificial Intelligence Research, 23, 667, 10.1613/jair.1542 Marx, 2002, Narcissists, stepmothers and spies Mundhenk, 2007, Undecidability of multi-modal hybrid logics, Electronic Notes in Theoretical Computer Science, 174, 29, 10.1016/j.entcs.2006.11.024 Ono, 1980, On the size of refutation Kripke models for some linear modal and tense logics, Studia Logica, 34, 325, 10.1007/BF00713542 Papadimitriou, 1994 Prior, 1967 Reynolds, 2003, The complexity of the temporal logic with “until” over general linear time, Journal of Computer and System Sciences, 66, 393, 10.1016/S0022-0000(03)00005-9 Sistla, 1985, The complexity of propositional linear temporal logics, Journal of the ACM, 32, 733, 10.1145/3828.3837 Edith Spaan, Complexity of modal logics, PhD thesis, ILLC, University of Amsterdam, 1993. Spaan, 1993, The complexity of propositional tense logics, 287 Larry Stockmeyer, The complexity of decision problems in automata and logic, PhD thesis, MIT, 1974. Wieslaw Szwast, Lidia Tendera, On the decision problem for the guarded fragment with transitivity, in: Proc. of the 16th LICS, IEEE Computer Society, 2001, pp. 147–156. ten Cate, 2005, Guarded fragments with constants, Journal of Logic, Language and Information, 14, 281, 10.1007/s10849-005-5787-x ten Cate, 2005, On the complexity of hybrid logics with binders, vol. 3634, 339