{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:44:15Z","timestamp":1742913855218,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540008972"},{"type":"electronic","value":"9783540365761"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36576-1_19","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:42:17Z","timestamp":1181616137000},"page":"299-312","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The Two-Variable Guarded Fragment with Transitive Guards Is 2EXPTIME-Hard"],"prefix":"10.1007","author":[{"given":"Emanuel","family":"Kiero\u0144ski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,28]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1004275029985","volume":"27","author":"H. Andr\u00e9ka","year":"1998","unstructured":"H. Andr\u00e9ka, J. van Benthem, I. N\u00e9meti.Modal Languages and Bounded Fragments of Predicate Logic.Journal of Philosophical Logic, 27, pages 217\u2013274,1998.","journal-title":"Journal of Philosophical Logic"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. Diaz, J. Gabarr\u00f3.Structural Complexity II Springer 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"A. Chandra, D. Kozen, L. Stockmeyer.Alternation.Journal of the ACM 28(1), pages 114\u2013133,1981","DOI":"10.1145\/322234.322243"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"H. Ganzinger, C. Meyer, M. Veanes.The Two-Variable Guarded Fragment with Transitive Relations.Proc. of 14-th IEEE Symp. on Logic in Computer Science (LICS)pages 24\u201334,1999.","DOI":"10.1109\/LICS.1999.782582"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.2307\/2586808","volume":"64","author":"Erich Gr\u00e4del","year":"1999","unstructured":"E. Gr\u00e4del.On the Restraining Power of Guards.Journal of Symbolic Logic 64:1719\u20131742,1999.","journal-title":"Journal of Symbolic Logic"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, M. Otto, E. Rosen.Undecidability Results on Two-Variable First-Order Logic.Bulletin of Symbolic Logic 3(1),pages 53\u201369,1997.","DOI":"10.2307\/421196"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/421196","volume":"3","author":"Erich Gr\u00e4del","year":"1997","unstructured":"E. Gr\u00e4del, P. Kolaitis, M. Vardi.On the Decision Problem for Two-Variable First Order Logic.Bulletin of Symbolic Logic 3(1),pages 53\u201396,1997.","journal-title":"Bulletin of Symbolic Logic"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, I. Walukiewicz.Guarded Fixpoint Logic.Proc. of 14-th IEEE Symp. on Logic in Computer Science (LICS)pages 45\u201354,1999.","DOI":"10.1109\/LICS.1999.782585"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"E. Kiero\u0144ski.EXPSPACE-Complete Variant of Guarded Fragment with Transitiv-ity.Proc. of 19-th International Symposium on Theoretical Aspects of Computer Science (STACS)pages 608\u2013619,2002.","DOI":"10.1007\/3-540-45841-7_50"},{"issue":"3","key":"19_CR10","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"Dexter Kozen","year":"1983","unstructured":"D. Kozen.Results on the Propositional \u03bc-Calculus.Theoretical Computer Science 27,pages 333\u2013354,1983.","journal-title":"Theoretical Computer Science"},{"key":"19_CR11","unstructured":"O. Kupferman, A. Pnueli.Once and For All.Proc. of 10-th IEEE Symp. on Logic in Computer Science (LICS)pages 25\u201335,1995."},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"Harry R. Lewis","year":"1980","unstructured":"H.R. Lewis.Complexity Results for Classes of Quantificational Formulas.Journal of Computer and System Sciences 21,pages 317\u2013353,1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"G. De Giacomo, F. Masacci.Tableaux and Algorithms for Propositional Dynamic Logic with Converse.Proc. of 13-th Int. Conf. on Automated Deduction (CADE) pages 613\u2013627,1996.","DOI":"10.1007\/3-540-61511-3_117"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/malq.19750210118","volume":"21","author":"M. Mortimer.On Languages with Two Variables","year":"1975","unstructured":"M. Mortimer.On Languages with Two Variables.Zeitschr. f. Logik und Grundlagen d. Math.21,pages 135\u2013140,1975.","journal-title":"Zeitschr. f. Logik und Grundlagen d. Math"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"V.R. Pratt.Models of Program Logics.Proc. of 20-th Annual Symposium on Foundations of Computer Science (FOCS)pages 115\u2013122,1979.","DOI":"10.1109\/SFCS.1979.24"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"M.O. Rabin.Decidability of Second-Order Theories and Automata on In finite Trees.Transactions of the American Mathematical Society 141,pages 1\u201335,1969.","DOI":"10.2307\/1995086"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"W. Szwast, L. Tendera.On the Decision Problem for the Guarded Fragment with Transitivity.Proc. of 16-th IEEE Symp. on Logic in Computer Science (LICS) pages 147\u2013156,2001.","DOI":"10.1109\/LICS.2001.932491"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi.Reasoning about The Past with Two-Way Automata.Proc.of 25-th International Colloquium on Automata, Languages, and Programming (ICALP) pages 628\u2013641,1998.","DOI":"10.1007\/BFb0055090"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36576-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:53:40Z","timestamp":1737093220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36576-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540008972","9783540365761"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-36576-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]},"assertion":[{"value":"28 February 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}