{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:34:43Z","timestamp":1768318483727,"version":"3.49.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":27,"publisher":"Springer-Verlag","isbn-type":[{"value":"354055789X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0023764","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T10:11:10Z","timestamp":1132395070000},"page":"149-163","source":"Crossref","is-referenced-by-count":18,"title":["On transitive closure logic"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati and S. Cosmadakis, Expressiveness of Restricted Recursive Queries, Proceedings of 21st ACM Symposium on Theory of Computing (1989), 113\u2013126.","DOI":"10.1145\/73007.73018"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"F. Afrati, S. Cosmadakis and M. Yannakakis, On Datalog vs. Polynomial Time, Proceedings of 10th ACM Symposium on Principles of Database Systems (1991).","DOI":"10.1145\/113413.113415"},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"J. Barwise, On Moschovakis closure ordinals, J. Symbolic Logic 42 (1977), 292\u2013296.","journal-title":"J. Symbolic Logic"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"J. Cai, M. F\u00fcrer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Proceedings of 30th IEEE Symposium on Foundations of Computer Science (1989), 612\u2013617.","DOI":"10.1109\/SFCS.1989.63543"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel, Structure and Complexity of Relational Queries, J. Comp. Syst. Sciences 25 (1982), 99\u2013128.","journal-title":"J. Comp. Syst. Sciences"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0743-1066(85)90002-0","volume":"1","author":"A. Chandra","year":"1985","unstructured":"A. Chandra and D. Harel, Horn Clause Queries and Generalizations, J. Logic Programming 1 (1985), 1\u201315.","journal-title":"J. Logic Programming"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"M. Consens and A. Mendelzon, GraphLog: a Visual Formalism for Real Life Recursion, Proceedings of 9th ACM Symposium on Principles of Database Systems (1990), 404\u2013416.","DOI":"10.1145\/298514.298591"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"E. Dahinaus, Skolem Normal Forms Concerning the Least Fixed Point, in: \u201cComputation Theory and Logic\u201d (E. B\u00f6rger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 101\u2013106.","DOI":"10.1007\/3-540-18170-9_158"},{"key":"11_CR9","unstructured":"H. D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic, Springer-Verlag, 1984."},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1961) 129\u2013141.","journal-title":"Fund. Math."},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin, Monadic generalized spectra, Zeitschrift f\u00fcr Math. Logik Grundlagen d. Math. 21 (1975), 89\u201396.","journal-title":"Zeitschrift f\u00fcr Math. Logik Grundlagen d. Math."},{"key":"11_CR12","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9, Sur quelques classifications des syst\u00e8mes de relations, Publications Scientifique de l' Universit\u00e9 d' Alger, S\u00e9rie A 1 (1954), 35\u2013182.","journal-title":"Publications Scientifique de l' Universit\u00e9 d' Alger, S\u00e9rie A"},{"key":"11_CR13","unstructured":"E. Gr\u00e4del and G. McColm, Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic, in preparation."},{"key":"11_CR14","unstructured":"Y. Gurevich, Logic and the Challenge of Computer Science, in: E. B\u00f6rger (Ed.), Trends in Theoretical Computer Science, Computer Science Press (1988), 1\u201357."},{"key":"11_CR15","first-page":"65","volume":"22","author":"N. Immerman","year":"1981","unstructured":"N. Immerman, Number of Quantifiers is Better than Number of Tape Cells, J. Comp. Syst. Sciences 22 (1981), 65\u201372.","journal-title":"J. Comp. Syst. Sciences"},{"key":"11_CR16","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman, Upper and lower bounds for first-order expressibility, J. Comp. Syst. Sciences 25 (1982), 76\u201398.","journal-title":"J. Comp. Syst. Sciences"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages that Capture Complexity Classes, SIAM J. Comput. 16 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"key":"11_CR18","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput. 17 (1988), 935\u2013939.","journal-title":"SIAM J. Comput."},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"N. Immerman, Descriptive and Computational Complexity, in: J. Hartmanis (Ed.), Computational Complexity Theory, Proc. of AMS Symposia in Appl. Math. 38 (1989), 75\u201391.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"11_CR20","first-page":"1073","volume-title":"Handbook of Theoretical Computer Science, vol. B","author":"P. Kannellakis","year":"1990","unstructured":"P. Kannellakis, Elements of Relational Database Theory, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science, vol. B, North Holland, Amsterdam 1990, pp. 1073\u20131156."},{"key":"11_CR21","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0890-5401(91)90059-B","volume":"90","author":"P. Kolaitis","year":"1991","unstructured":"Ph. Kolaitis, The Expressive Power of Stratified Logic Programs, Information and Computation 90 (1991), 50\u201366.","journal-title":"Information and Computation"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Vardi, On the Expressive Power of Datalog: Tools and a Case Study, Proceeding of 9th ACM Symposium on Principles of Database Systems (1990), 61\u201371.","DOI":"10.1145\/298514.298542"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Vardi, 0-1 Laws for Infinitary Logics, Proceedings of 5th IEEE Symposium on Logic in Computer Science (1990), 156\u2013167.","DOI":"10.1109\/LICS.1990.113742"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"V. Lakshmanan and A. Mendelzon, Inductive pebble games and the expressive power of datalog, Proceedings of 8th ACM Symposium on Principles of Database Systems (1989), 301\u2013310.","DOI":"10.1145\/73721.73751"},{"key":"11_CR25","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi, The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica 26, (1988), 279\u2013284.","journal-title":"Acta Informatica"},{"key":"11_CR26","unstructured":"A. Van Gelder, Negation as Failure using tight derivations for general logic programs, Proceedings of 3rd IEEE Symposium on Logic Programming (1986), 137\u2013146."},{"key":"11_CR27","unstructured":"M. Zloof, Query-by-Example: Operations on the Transitive Closure, IBM Research Report RC5526 (1976)."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023764.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:50:30Z","timestamp":1607550630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354055789X"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0023764","relation":{},"subject":[]}}