{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:12Z","timestamp":1761611172754},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11672142_41","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"500-511","source":"Crossref","is-referenced-by-count":12,"title":["Generalized Modal Satisfiability"],"prefix":"10.1007","author":[{"given":"Michael","family":"Bauland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Schnoor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilka","family":"Schnoor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"41_CR1","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. SIGACT News\u00a034(4), 38\u201352 (2003)","journal-title":"SIGACT News"},{"issue":"1","key":"41_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News\u00a035(1), 22\u201335 (2004)","journal-title":"SIGACT News"},{"key":"41_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal logic","author":"P. Blackburn","year":"2001","unstructured":"Blackburn, P., de Rijke, M., Venema, Y.: Modal logic. Cambridge University Press, New York (2001)"},{"issue":"1-2","key":"41_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.artint.2003.02.001","volume":"153","author":"B. Bennett","year":"2004","unstructured":"Bennett, B., Galton, A.: A unifying semantics for time and events. Artificial Intelligence\u00a0153(1-2), 13\u201348 (2004)","journal-title":"Artificial Intelligence"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Bauland, M., Hemaspaandra, E., Schnoor, H., Schnoor, I.: Generalized modal satisfiability. Technical report, Theoretical Computer Science, University of Hannover (2005)","DOI":"10.1007\/11672142_41"},{"issue":"1-2","key":"41_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.artint.2005.01.005","volume":"164","author":"C. Baral","year":"2005","unstructured":"Baral, C., Zhang, Y.: Knowledge updates: Semantics and complexity issues. Artificial Intelligence\u00a0164(1-2), 209\u2013243 (2005)","journal-title":"Artificial Intelligence"},{"key":"41_CR7","unstructured":"Dalmau, V.: Computational Complexity of Problems over Generalized Formulas. PhD thesis, Department de Llenguatges i Sistemes Inform\u00e0tica, Universitat Polit\u00e9cnica de Catalunya (2000)"},{"issue":"2-3","key":"41_CR8","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":"41_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1997.2625","volume":"134","author":"F. Donini","year":"1997","unstructured":"Donini, F., Lenzerini, M., Nardi, D., Nutt, W.: The complexity of concept languages. Information and Computation\u00a0134, 1\u201358 (1997)","journal-title":"Information and Computation"},{"issue":"1","key":"41_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0004-3702(00)00070-9","volume":"124","author":"F. Donini","year":"2000","unstructured":"Donini, F., Massacci, F.: EXPTIME tableaux for ALC. Artificial Intelligence\u00a0124(1), 87\u2013138 (2000)","journal-title":"Artificial Intelligence"},{"key":"41_CR11","first-page":"171","volume-title":"TARK 1986: Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning About Knowledge","author":"M. Fischer","year":"1986","unstructured":"Fischer, M., Immerman, N.: Foundations of knowledge for distributed systems. In: TARK 1986: Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning About Knowledge, pp. 171\u2013185. Morgan Kaufmann Publishers Inc., San Francisco (1986)"},{"key":"41_CR12","first-page":"34","volume":"4","author":"K. G\u00f6del","year":"1933","unstructured":"G\u00f6del, K.: Eine Interpretation des intuitionistischen Aussagenkalk\u00fcls. Ergebnisse eines mathematischen Kolloquiums\u00a04, 34\u201340 (1933)","journal-title":"Ergebnisse eines mathematischen Kolloquiums"},{"issue":"5-6","key":"41_CR13","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1570-8683(03)00008-9","volume":"1","author":"R. Goldblatt","year":"2003","unstructured":"Goldblatt, R.: Mathematical modal logic: A view of its evolution. Journal of Applied Logic\u00a01(5-6), 309\u2013392 (2003)","journal-title":"Journal of Applied Logic"},{"issue":"2","key":"41_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0004-3702(95)00018-A","volume":"75","author":"J. Halpern","year":"1995","unstructured":"Halpern, J.: The effect of bounding the number of primitive propositional and the depth of nesting on the complexity of modal logic. Artificial Intelligence\u00a075(2), 361\u2013372 (1995)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"41_CR15","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:\u00a0[Hem05]","journal-title":"Journal of Logic and Computation"},{"key":"41_CR16","unstructured":"E.\u00a0Hemaspaandra. The Complexity of Poor Man\u2019s Logic, CoRR, cs.LO\/9911014 (1999) (revised 2005)"},{"issue":"2","key":"41_CR17","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0004-3702(92)90049-4","volume":"54","author":"J. Halpern","year":"1992","unstructured":"Halpern, J., Moses, Y.: A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence\u00a054(2), 319\u2013379 (1992)","journal-title":"Artificial Intelligence"},{"key":"41_CR18","first-page":"132","volume-title":"STOC 1988: Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"J. Halpern","year":"1988","unstructured":"Halpern, J., Moses, Y., Tuttle, M.: A knowledge-based analysis of zero knowledge. In: STOC 1988: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 132\u2013147. ACM Press, New York (1988)"},{"issue":"4","key":"41_CR19","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1002\/malq.19630090502","volume":"9","author":"S. Kripke","year":"1963","unstructured":"Kripke, S.: A semantical analysis of modal logic I: Normal modal propositional calculi. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik\u00a09, 67\u201396 (1963)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"41_CR21","first-page":"83","volume":"16","author":"S. Kripke","year":"1963","unstructured":"Kripke, S.: Semantical considerations on modal logic. Acta Philosophica Fennica\u00a016, 83\u201394 (1963)","journal-title":"Acta Philosophica Fennica"},{"issue":"3","key":"41_CR22","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":"41_CR23","volume-title":"A Survey of Symbolic Logic","author":"C. Lewis","year":"1918","unstructured":"Lewis, C.: A Survey of Symbolic Logic. University of California Press, Berkley (1918)"},{"key":"41_CR24","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. Mathematical Systems Theory\u00a013, 45\u201353 (1979)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"41_CR25","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0004-3702(03)00063-8","volume":"149","author":"C.-J. Liau","year":"2003","unstructured":"Liau, C.-J.: Belief, information acquisition, and trust in multi-agent systems \u2013 a modal logic formulation. Artificial Intelligence\u00a0149(1), 31\u201360 (2003)","journal-title":"Artificial Intelligence"},{"key":"41_CR26","unstructured":"Lewis, C., Langford, C.: Symbolic Logic. Dover (1932)"},{"key":"41_CR27","first-page":"207","volume-title":"TARK 1986: Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning About Knowledge","author":"R. Ladner","year":"1986","unstructured":"Ladner, R., Reif, J.: The logic of distributed protocols: Preliminary report. In: TARK 1986: Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning About Knowledge, pp. 207\u2013222. Morgan Kaufmann Publishers Inc., San Francisco (1986)"},{"key":"41_CR28","unstructured":"Lemmon, E., Scott, D.: An introduction to modal logic - the \u2019Lemmon Notes\u2019 (1977)"},{"key":"41_CR29","unstructured":"Moore, R.: Reasoning about knowledge and action. Technical Report 191, AI Center, SRI International, 333 Ravenswood Ave, Menlo Park, CA 94025 (1979)"},{"key":"41_CR30","doi-asserted-by":"crossref","unstructured":"McCarthy, J., Sato, M., Hayashi, T., Igarashi, S.: On the model theory of knowledge. Technical report, Stanford, CA, USA (1978)","DOI":"10.21236\/ADA065502"},{"key":"41_CR31","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-32275-7_18","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"G. Nordh","year":"2005","unstructured":"Nordh, G.: A trichotomy in the complexity of propositional circumscription. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 257\u2013269. Springer, Heidelberg (2005)"},{"key":"41_CR32","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":"41_CR33","unstructured":"Reith, S.: Generalized Satisfiability Problems. PhD thesis, Fachbereich Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (2001)"},{"key":"41_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/3-540-44612-5_59","volume-title":"Mathematical Foundations of Computer Science 2000","author":"S. Reith","year":"2000","unstructured":"Reith, S., Vollmer, H.: Optimal satisfiability for propositional calculi and constraint satisfaction problems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 640\u2013649. Springer, Heidelberg (2000)"},{"key":"41_CR35","unstructured":"Reith, S., Wagner, K.: The complexity of problems defined by Boolean circuits. Technical Report 255, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg. In: Proceedings of the International Conference on Mathematical Foundation of Informatics, Hanoi, October 25\u201328, 1999 (2000)"},{"issue":"3","key":"41_CR36","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1145\/3828.3837","volume":"32","author":"A. Sistla","year":"1985","unstructured":"Sistla, A., Clarke, E.: The complexity of propositional linear temporal logics. Journal of the ACM\u00a032(3), 733\u2013749 (1985)","journal-title":"Journal of the ACM"},{"key":"41_CR37","unstructured":"Schnoor, H.: The complexity of the Boolean formula value problem. Technical report, Theoretical Computer Science, University of Hannover (2005)"},{"key":"41_CR38","unstructured":"Segerberg, K.: An Essay in Classical Modal Logic. Filosofiska studier 13, University of Uppsala (1971)"},{"issue":"1","key":"41_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(91)90078-X","volume":"48","author":"M. Schmidt-Schauss","year":"1991","unstructured":"Schmidt-Schauss, M., Smolka, G.: Attributive concept descriptions with complements. Artificial Intelligence\u00a048(1), 1\u201326 (1991)","journal-title":"Artificial Intelligence"},{"key":"41_CR40","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity \u2013 A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity \u2013 A Uniform Approach. Texts in Theoretical Computer Science. Springer, Berlin, Heidelberg (1999)"},{"key":"41_CR41","volume-title":"An Essay in Modal Logic","author":"G. Wright von","year":"1951","unstructured":"von Wright, G.: An Essay in Modal Logic. North-Holland Publishing Company, Amsterdam (1951)"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T23:31:39Z","timestamp":1555457499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/11672142_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}