{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T23:18:43Z","timestamp":1761607123250,"version":"build-2065373602"},"reference-count":42,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9780444516909"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1016\/s1570-2464(07)80006-1","type":"book-chapter","created":{"date-parts":[[2007,10,4]],"date-time":"2007-10-04T09:38:50Z","timestamp":1191490730000},"page":"139-179","source":"Crossref","is-referenced-by-count":10,"title":["3 Complexity of modal logic"],"prefix":"10.1016","member":"78","reference":[{"year":"1995","series-title":"Foundations of Databases","author":"Abiteboul","key":"10.1016\/S1570-2464(07)80006-1_bib1"},{"issue":"3","key":"10.1016\/S1570-2464(07)80006-1_bib2","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1004275029985","article-title":"Modal languages and bounded fragments of predicate logic","volume":"27","author":"Andr\u00e9ka","year":"1998","journal-title":"Journal of Philosophical Logic"},{"year":"2002","series-title":"Description Logic Handbook","key":"10.1016\/S1570-2464(07)80006-1_bib3"},{"year":"2001","series-title":"Modal Logic","author":"Blackburn","key":"10.1016\/S1570-2464(07)80006-1_bib4"},{"year":"1997","series-title":"The Classical Decision Problem","author":"Borger","key":"10.1016\/S1570-2464(07)80006-1_bib5"},{"key":"10.1016\/S1570-2464(07)80006-1_bib6","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","article-title":"Domino-tiling games","volume":"32","author":"Chlebus","year":"1986","journal-title":"J. Comput. Syst. Sci."},{"year":"1999","series-title":"Model checking","author":"Clarke","key":"10.1016\/S1570-2464(07)80006-1_bib7"},{"year":"2000","series-title":"Model checking","author":"Clarke","key":"10.1016\/S1570-2464(07)80006-1_bib8"},{"key":"10.1016\/S1570-2464(07)80006-1_bib9","series-title":"Proc. 3rd ACM SYMP. on Theory of Computing","first-page":"151","article-title":"The complexity of theorem proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/S1570-2464(07)80006-1_bib10","series-title":"Perspectives in Mathematical Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03182-7","article-title":"Finite Model Theory","author":"Ebbinghaus","year":"1995"},{"key":"10.1016\/S1570-2464(07)80006-1_bib11","series-title":"Proceedings of the 29th IEEE Symposium on Foundations of Computer Science","first-page":"328","article-title":"The complexity of tree automata and logics of programs","author":"Emerson","year":"1988"},{"key":"10.1016\/S1570-2464(07)80006-1_bib12","series-title":"PhD thesis","article-title":"Contributions to the Model Theory of Finite Structures","author":"Fagin","year":"1973"},{"year":"1995","series-title":"Reasoning about Knowledge","author":"Fagin","key":"10.1016\/S1570-2464(07)80006-1_bib13"},{"issue":"2","key":"10.1016\/S1570-2464(07)80006-1_bib14","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","article-title":"Propositional dynamic logic of regular programs","volume":"18","author":"Fisher","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S1570-2464(07)80006-1_bib15","series-title":"Number 148 in Studies in Logic and the Foundations of Mathematics","article-title":"Many-Dimensional Modal Logics: Theory and Applica- tions","author":"Gabbay","year":"2003"},{"year":"1979","series-title":"Computers and Intractibility. A Guide to the Theory of NP-Completeness","author":"Garey","key":"10.1016\/S1570-2464(07)80006-1_bib16"},{"issue":"4","key":"10.1016\/S1570-2464(07)80006-1_bib17","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.2307\/2586808","article-title":"On the restraining power of guards","volume":"64","author":"Gr\u00e4del","year":"1999","journal-title":"Journal of Symbolic Logic"},{"issue":"1","key":"10.1016\/S1570-2464(07)80006-1_bib18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/421196","article-title":"On the decision problem for two-variable first order logic","volume":"3","author":"Gr\u00e4del","year":"1997","journal-title":"Bulletin of Symbolic Logic"},{"issue":"2","key":"10.1016\/S1570-2464(07)80006-1_bib19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0004-3702(95)00018-A","article-title":"The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic","volume":"75","author":"Halpem","year":"1995","journal-title":"Artificiall Intelligence"},{"key":"10.1016\/S1570-2464(07)80006-1_bib20","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0004-3702(92)90049-4","article-title":"A guide to completeness and complexity for modal logics of knowledge and belief","volume":"54","author":"Halpem","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1570-2464(07)80006-1_bib21","series-title":"Proc. of the Conference on Foundations of Computing Theory, volume 158 of LNCS","first-page":"177","article-title":"Recurring dominoes: making the highly undecidable highly understandable","author":"Harel","year":"1983"},{"key":"10.1016\/S1570-2464(07)80006-1_bib22","first-page":"51","article-title":"Recurring dominoes: making the highly undecidable highly understandable","volume":"24","author":"Harel","year":"1985","journal-title":"Annals of Discrete Mathemat- ics"},{"year":"1998","series-title":"Descriptive Complexity","author":"Immerman","key":"10.1016\/S1570-2464(07)80006-1_bib23"},{"key":"10.1016\/S1570-2464(07)80006-1_bib24","series-title":"Proceedings of the Conference on Automated Deduction, volume 2392 of Lecture Notes in Artificial Intelligence","article-title":"The complexity of the graded mu-calculus","author":"Kupferman","year":"2002"},{"issue":"3","key":"10.1016\/S1570-2464(07)80006-1_bib25","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0206033","article-title":"The computational complexity of provability in systems of modal propositional logic","volume":"6","author":"Ladner","year":"1977","journal-title":"SIAM journal of computing"},{"key":"10.1016\/S1570-2464(07)80006-1_bib26","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","article-title":"Complexity results for classes of quantificational formulas","volume":"21","author":"Lewis","year":"1980","journal-title":"Journal of Computer and System Sciences"},{"year":"1998","series-title":"Elements of the Theory of Computation","author":"Lewis","key":"10.1016\/S1570-2464(07)80006-1_bib27"},{"year":"2004","series-title":"Elements of Finite Model Theory","author":"Libkin","key":"10.1016\/S1570-2464(07)80006-1_bib28"},{"key":"10.1016\/S1570-2464(07)80006-1_bib29","series-title":"Applied Logic Series","article-title":"Multi-dimensional Modal Logic","author":"Marx","year":"1997"},{"key":"10.1016\/S1570-2464(07)80006-1_bib30","series-title":"Finite Model Theory and its Applications","article-title":"Local variations on a loose theme: modal logic and decidability","author":"Marx","year":"2004"},{"key":"10.1016\/S1570-2464(07)80006-1_bib31","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/malq.19750210118","article-title":"On languages with two variables","volume":"21","author":"Mortimer","year":"1975","journal-title":"Zeitsch.f math. Logik und Grundlagen d. Math."},{"year":"1994","series-title":"Computational Complexity","author":"Papadimitriou","key":"10.1016\/S1570-2464(07)80006-1_bib32"},{"key":"10.1016\/S1570-2464(07)80006-1_bib33","series-title":"Proceedings of the 20th IEEE symposium on Foundations of Computer Science","first-page":"115","article-title":"Models of program logics","author":"Pratt","year":"1979"},{"key":"10.1016\/S1570-2464(07)80006-1_bib34","series-title":"Proceedings of the International Joint Conference on Automated Reasoning, volume 2083 of LNAI","first-page":"76","article-title":"The hybrid mu-calculus","author":"Sattler","year":"2001"},{"issue":"3","key":"10.1016\/S1570-2464(07)80006-1_bib35","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/3828.3837","article-title":"Complexity of propositional linear temporal logics","volume":"32","author":"Sistla","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S1570-2464(07)80006-1_bib36","series-title":"PhD thesis","article-title":"Complexity of modal logics","author":"Spaan","year":"1993"},{"key":"10.1016\/S1570-2464(07)80006-1_bib37","series-title":"Complexity, Logic and Recursion Theory, volume 187 of Lecture notes in pure and applied mathematics","first-page":"331","article-title":"The convenience of tilings","author":"van Emde Boas","year":"1997"},{"key":"10.1016\/S1570-2464(07)80006-1_bib38","series-title":"Proceedings of the ACM 14th Symposium on Principles of Database Systems","first-page":"266","article-title":"On the complexity of bounded-variable queries","author":"Vardi","year":"1995"},{"key":"10.1016\/S1570-2464(07)80006-1_bib39","first-page":"149","article-title":"Why is modal logic so robustly decidable?","volume":"31","author":"Vardi","year":"1997"},{"key":"10.1016\/S1570-2464(07)80006-1_bib40","doi-asserted-by":"crossref","first-page":"628+","DOI":"10.1007\/BFb0055090","article-title":"Reasoning about the past with two-way automata","volume":"1443","author":"Vardi","year":"1998","journal-title":"Lecture Notes in Computer Science"},{"key":"10.1016\/S1570-2464(07)80006-1_bib41","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0022-0000(86)90026-7","article-title":"Automata-theoretic techniques for modal logics of programs","volume":"32","author":"Vardi","year":"1986","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/S1570-2464(07)80006-1_bib42","doi-asserted-by":"crossref","first-page":"591","DOI":"10.2307\/2275853","article-title":"Cylindric modal logic","volume":"60","author":"Venema","year":"1995","journal-title":"Journal of Symbolic Logic"}],"container-title":["Studies in Logic and Practical Reasoning","Handbook of Modal Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570246407800061?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570246407800061?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T23:15:21Z","timestamp":1761606921000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1570246407800061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9780444516909"],"references-count":42,"URL":"https:\/\/doi.org\/10.1016\/s1570-2464(07)80006-1","relation":{},"ISSN":["1570-2464"],"issn-type":[{"type":"print","value":"1570-2464"}],"subject":[],"published":{"date-parts":[[2007]]}}}