{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:27:51Z","timestamp":1740461271783,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_51","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"580-591","source":"Crossref","is-referenced-by-count":0,"title":["Does Treewidth Help in Modal Satisfiability?"],"prefix":"10.1007","author":[{"given":"M.","family":"Praveen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Achilleos, A., Lampis, M., Mitsou, V.: Parameterized modal satisfiability. In: ICALP, arXiv:0912.4941v1 (to appear 2010)","key":"51_CR1","DOI":"10.1007\/978-3-642-14162-1_31"},{"key":"51_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-04027-6_8","volume-title":"Computer Science Logic","author":"I. Adler","year":"2009","unstructured":"Adler, I., Weyer, M.: Tree-width for first order formulae. In: Gr\u00e4del, E., Kahle, R. (eds.) CSL 2009. LNCS, vol.\u00a05771, pp. 71\u201385. Springer, Heidelberg (2009)"},{"key":"51_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal Logic","author":"P. Blackburn","year":"2001","unstructured":"Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. CUP, Cambridge (2001)"},{"issue":"8","key":"51_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"51_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Alg.\u00a021(2), 358\u2013402 (1996)","journal-title":"J. Alg."},{"key":"51_CR6","first-page":"161","volume-title":"ECAI","author":"H. Chen","year":"2004","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: de M\u00e1ntaras, R.L., Saitta, L. (eds.) ECAI, pp. 161\u2013165. IOS Press, Amsterdam (2004)"},{"key":"51_CR7","first-page":"257","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues. ITA\u00a026, 257\u2013286 (1992)","journal-title":"ITA"},{"key":"51_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 310\u2013326. Springer, Heidelberg (2002)"},{"issue":"1","key":"51_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(89)90137-0","volume":"65","author":"P. Enjalbert","year":"1989","unstructured":"Enjalbert, P., del Cerro, L.F.: Modal resolution in clausal form. Theor. Comp. Sc.\u00a065(1), 1\u201333 (1989)","journal-title":"Theor. Comp. Sc."},{"key":"51_CR10","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning About Knowledge","author":"R. Fagin","year":"1995","unstructured":"Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning About Knowledge. MIT Press, Cambridge (1995)"},{"key":"51_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-540-73556-4_38","volume-title":"Combinatorial Optimization and Applications","author":"M. Fellows","year":"2007","unstructured":"Fellows, M., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA. LNCS, vol.\u00a04616, pp. 366\u2013377. Springer, Heidelberg (2007)"},{"issue":"4","key":"51_CR12","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Disc. App. Math.\u00a0156(4), 511\u2013529 (2008)","journal-title":"Disc. App. Math."},{"key":"51_CR13","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"unstructured":"Gr\u00e4del, E.: Why are modal logics so robustly decidable? In: Current Trends in Theor. Comp. Sc., pp. 393\u2013408 (2001)","key":"51_CR14"},{"key":"51_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/11821069_5","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M. Grohe","year":"2006","unstructured":"Grohe, M.: The structure of tractable constraint satisfaction problems. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 58\u201372. Springer, Heidelberg (2006)"},{"issue":"2","key":"51_CR16","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0004-3702(95)00018-A","volume":"75","author":"J.Y. Halpern","year":"1995","unstructured":"Halpern, J.Y.: The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic. Artif. Intell.\u00a075(2), 361\u2013372 (1995)","journal-title":"Artif. Intell."},{"issue":"3","key":"51_CR17","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0004-3702(92)90049-4","volume":"54","author":"J.Y. Halpern","year":"1992","unstructured":"Halpern, J.Y., Moses, Y.O.: A guide to completeness and complexity for modal logics of knowledge and belief. Artif. Intell.\u00a054(3), 319\u2013379 (1992)","journal-title":"Artif. Intell."},{"doi-asserted-by":"crossref","unstructured":"Halpern, J.Y., R\u00eago, L.C.: Characterizing the np-pspace gap in the satisfiability problem for modal logic. In: IJCAI, pp. 2306\u20132311 (2007)","key":"51_CR18","DOI":"10.1093\/logcom\/exm029"},{"unstructured":"Hemaspaandra, E., Schnoor, H.: On the complexity of elementary modal logics. In: STACS, pp. 349\u2013360 (2008)","key":"51_CR19"},{"key":"51_CR20","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-87803-2_19","volume-title":"Logics in Artificial Intelligence","author":"A. Herzig","year":"2008","unstructured":"Herzig, A., Mengin, J.: Uniform interpolation by resolution in modal logic. In: H\u00f6lldobler, S., Lutz, C., Wansing, H. (eds.) JELIA 2008. LNCS (LNAI), vol.\u00a05293, pp. 219\u2013231. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Hustadt, U., Schmidt, R.A.: An empirical analysis of modal theorem provers. J. Applied Non-Classical Logics\u00a09(4) (1999)","key":"51_CR21","DOI":"10.1080\/11663081.1999.10510981"},{"key":"51_CR22","first-page":"407","volume-title":"LICS 2009","author":"Y. Kazakov","year":"2009","unstructured":"Kazakov, Y., Pratt-Hartmann, I.: A note on the complexity of the satisfiability problem for graded modal logics. In: LICS 2009, pp. 407\u2013416. IEEE Computer Society, Los Alamitos (2009)"},{"issue":"3","key":"51_CR23","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0206033","volume":"6","author":"R.E. Ladner","year":"1977","unstructured":"Ladner, R.E.: The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput.\u00a06(3), 467\u2013480 (1977)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Marx, D.: Can you beat treewidth? In: FOCS, pp. 169\u2013179 (2007)","key":"51_CR24","DOI":"10.1109\/FOCS.2007.27"},{"unstructured":"Nguyen, L.A.: On the complexity of fragments of modal logics. Advances in Modal logic, vol.\u00a05, pp. 249\u2013268 (2005)","key":"51_CR25"},{"key":"51_CR26","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-540-45085-6_7","volume-title":"Automated Deduction \u2013 CADE-19","author":"G. Pan","year":"2003","unstructured":"Pan, G., Vardi, M.Y.: Optimizing a BDD-based modal solver. In: Baader, F. (ed.) CADE 2003. LNCS (LNAI), vol.\u00a02741, pp. 75\u201389. Springer, Heidelberg (2003)"},{"key":"51_CR27","first-page":"27","volume-title":"LICS 2006","author":"G. Pan","year":"2006","unstructured":"Pan, G., Vardi, M.Y.: Fixed-parameter hierarchies inside pspace. In: LICS 2006, pp. 27\u201336. IEEE Computer Society, Los Alamitos (2006)"},{"issue":"2-3","key":"51_CR28","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF00370324","volume":"39","author":"V.R. Pratt","year":"1980","unstructured":"Pratt, V.R.: Application of modal logic to programming. Studia Logica\u00a039(2-3), 257\u2013274 (1980)","journal-title":"Studia Logica"},{"key":"51_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/BFb0036943","volume-title":"Automata, Languages and Programming","author":"J.H. Reif","year":"1983","unstructured":"Reif, J.H., Sistla, A.P.: A multiprocess network logic with temporal and spatial modalities. In: D\u00edaz, J. (ed.) ICALP 1983. LNCS, vol.\u00a0154, pp. 629\u2013639. Springer, Heidelberg (1983)"},{"issue":"2","key":"51_CR30","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M. Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci.\u00a076(2), 103\u2013114 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"10","key":"51_CR31","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.ipl.2009.01.012","volume":"109","author":"B. Cate ten","year":"2009","unstructured":"ten Cate, B.: A note on the expressibility problem for modal logics and star-free regular expressions. Inf. Process. Lett.\u00a0109(10), 509\u2013513 (2009)","journal-title":"Inf. Process. Lett."},{"key":"51_CR32","first-page":"149","volume-title":"Descriptive Complexity and Finite Models","author":"M.Y. Vardi","year":"1996","unstructured":"Vardi, M.Y.: Why is modal logic so robustly decidable? In: Descriptive Complexity and Finite Models, pp. 149\u2013184. AMS, Providence (1996)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:31:53Z","timestamp":1740400313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_51"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}