{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:54:10Z","timestamp":1773939250662,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642038150","type":"print"},{"value":"9783642038167","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_50","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"587-599","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Satisfiability for Fragments of Hybrid Logic\u2014Part I"],"prefix":"10.1007","author":[{"given":"Arne","family":"Meier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Mundhenk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Thomas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Weber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Weiss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"50_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-48168-0_22","volume-title":"Computer Science Logic","author":"C. Areces","year":"1999","unstructured":"Areces, C., Blackburn, P., Marx, M.: A road-map on complexity for hybrid logics. In: Flum, J., Rodr\u00edguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol.\u00a01683, pp. 307\u2013321. Springer, Heidelberg (1999)"},{"issue":"5","key":"50_CR2","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1093\/jigpal\/8.5.653","volume":"8","author":"C. Areces","year":"2000","unstructured":"Areces, C., Blackburn, P., Marx, M.: The computational complexity of hybrid temporal logics. Logic Journal of the IGPL\u00a08(5), 653\u2013679 (2000)","journal-title":"Logic Journal of the IGPL"},{"key":"50_CR3","unstructured":"Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: DL-Lite in the light of first-order logic. In: Proc. AAAI 2007, pp. 361\u2013366 (2007)"},{"key":"50_CR4","doi-asserted-by":"crossref","unstructured":"Baader, F.: Terminological cycles in a description logic with existential restrictions. In: Proc. IJCAI 2003, pp. 325\u2013330 (2003)","DOI":"10.25368\/2022.120"},{"key":"50_CR5","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the $\\mathcal{EL}$ envelope. In: Proc. IJCAI 2005, pp. 364\u2013369 (2005)"},{"key":"50_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/11672142_41","volume-title":"STACS 2006","author":"M. Bauland","year":"2006","unstructured":"Bauland, M., Hemaspaandra, E., Schnoor, H., Schnoor, I.: Generalized modal satisfiability. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 500\u2013511. Springer, Heidelberg (2006)"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Bauland, M., Mundhenk, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The tractability of model checking for LTL: the good, the bad, and the ugly fragments. In: Proc. M4M-5 (2007). ENTCS, vol.\u00a0231, pp. 277\u2013292 (2009)","DOI":"10.1016\/j.entcs.2009.02.041"},{"key":"50_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-71389-0_5","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Bauland","year":"2007","unstructured":"Bauland, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The complexity of generalized satisfiability for linear temporal logic. In: Seidl, H. (ed.) FOSSACS 2007. LNCS, vol.\u00a04423, pp. 48\u201362. Springer, Heidelberg (2007)"},{"key":"50_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01048404","volume":"4","author":"P. Blackburn","year":"1995","unstructured":"Blackburn, P., Seligman, J.: Hybrid languages. JoLLI\u00a04, 41\u201362 (1995)","journal-title":"JoLLI"},{"issue":"4","key":"50_CR10","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. ACM-SIGACT Newsletter\u00a034(4), 38\u201352 (2003)","journal-title":"ACM-SIGACT Newsletter"},{"key":"50_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-87803-2_6","volume-title":"Logics in Artificial Intelligence","author":"L. Bozzelli","year":"2008","unstructured":"Bozzelli, L., Lanotte, R.: Complexity and succinctness issues for linear-time hybrid logics. In: H\u00f6lldobler, S., Lutz, C., Wansing, H. (eds.) JELIA 2008. LNCS, vol.\u00a05293, pp. 48\u201361. Springer, Heidelberg (2008)"},{"key":"50_CR12","unstructured":"Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: DL-Lite: Tractable description logics for ontologies. In: Proc. AAAI 2005, pp. 602\u2013607 (2005)"},{"issue":"2-3","key":"50_CR13","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0004-3702(92)90076-A","volume":"53","author":"F. Donini","year":"1992","unstructured":"Donini, F., Hollunder, B., Lenzerini, M., Nardi, D., Nutt, W., Spaccamela, A.: The complexity of existential quantification in concept languages. Artificial Intelligence\u00a053(2-3), 309\u2013327 (1992)","journal-title":"Artificial Intelligence"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"Franceschet, M., de Rijke, M., Schlingloff, B.: Hybrid logics on linear structures: Expressivity and complexity. In: Proc. 10th TIME, pp. 166\u2013173 (2003)","DOI":"10.1109\/TIME.2003.1214893"},{"issue":"1","key":"50_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00215625","volume":"5","author":"V. Goranko","year":"1996","unstructured":"Goranko, V.: Hierarchies of modal and temporal logics with reference pointers. Journal of Logic, Language and Information\u00a05(1), 1\u201324 (1996)","journal-title":"Journal of Logic, Language and Information"},{"issue":"4","key":"50_CR16","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1093\/logcom\/11.4.609","volume":"11","author":"E. Hemaspaandra","year":"2001","unstructured":"Hemaspaandra, E.: The complexity of poor man\u2019s logic. Journal of Logic and Computation\u00a011(4), 609\u2013622 (2001); Corrected version available at arXiv (2005)","journal-title":"Journal of Logic and Computation"},{"issue":"3","key":"50_CR17","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0206033","volume":"6","author":"R. Ladner","year":"1977","unstructured":"Ladner, R.: The computational complexity of provability in systems of modal propositional logic. SIAM Journal on Computing\u00a06(3), 467\u2013480 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR18","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H. Lewis","year":"1979","unstructured":"Lewis, H.: Satisfiability problems for propositional calculi. Math. Sys. Theory\u00a013, 45\u201353 (1979)","journal-title":"Math. Sys. Theory"},{"key":"50_CR19","unstructured":"Meier, A., Mundhenk, M., Schneider, T., Thomas, M., Weber, V., Weiss, F.: The complexity of satisfiability for fragments of hybrid logic \u2014 Part I (2009), http:\/\/arxiv.org\/abs\/0906.1489"},{"key":"#cr-split#-50_CR20.1","unstructured":"Mundhenk, M., Schneider, T.: The complexity of hybrid logics over equivalence relations. In: Proc. HyLo, pp. 81???90 (2007);"},{"key":"#cr-split#-50_CR20.2","unstructured":"To appear in J. of Logic, Language and Information"},{"key":"50_CR21","unstructured":"Mundhenk, M., Schneider, T., Schwentick, T., Weber, V.: Complexity of hybrid logics over transitive frames. In: Proc. M4M-4 (2005), http:\/\/arxiv.org\/abs\/0806.4130"},{"key":"50_CR22","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"50_CR23","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"50_CR24","first-page":"1","volume":"5","author":"E. Post","year":"1941","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"key":"50_CR25","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0304-3975(96)00288-5","volume":"188","author":"K. Regan","year":"1997","unstructured":"Regan, K., Vollmer, H.: Gap-languages and log-time complexity classes. Theoretical Computer Science\u00a0188, 101\u2013116 (1997)","journal-title":"Theoretical Computer Science"},{"key":"50_CR26","first-page":"216","volume-title":"Proc. STOC","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. STOC, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"50_CR27","unstructured":"Schneider, T.: The Complexity of Hybrid Logics over Restricted Classes of Frames. PhD thesis, Univ. of Jena (2007)"},{"key":"50_CR28","unstructured":"Schnoor, H.: Algebraic Techniques for Satisfiability Problems. PhD thesis, Univ. of Hannover (2007)"},{"key":"50_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-540-70918-3_48","volume-title":"STACS 2007","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T., Weber, V.: Bounded-variable fragments of hybrid logics. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 561\u2013572. Springer, Heidelberg (2007)"},{"key":"50_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/11538363_24","volume-title":"Computer Science Logic","author":"B. Cate ten","year":"2005","unstructured":"ten Cate, B., Franceschet, M.: On the complexity of hybrid logics with binders. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, pp. 339\u2013354. Springer, Heidelberg (2005)"},{"key":"50_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Heidelberg (1999)"},{"key":"#cr-split#-50_CR32.1","unstructured":"Weber, V.: Hybrid branching-time logics. In: Proc. of HyLo, pp. 51???60 (2007);"},{"key":"#cr-split#-50_CR32.2","unstructured":"Accepted for a special issue of the J. of Logic, Language and Information"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T19:57:40Z","timestamp":1739303860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}