{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:53:39Z","timestamp":1725537219953},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642040269"},{"type":"electronic","value":"9783642040276"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-04027-6_4","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T17:27:52Z","timestamp":1252949272000},"page":"20-23","source":"Crossref","is-referenced-by-count":2,"title":["Fixed-Point Definability and Polynomial Time"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0168-0072(99)00005-6","volume":"100","author":"A. Blass","year":"1999","unstructured":"Blass, A., Gurevich, Y., Shelah, S.: Choiceless polynomial time. Annals of Pure and Applied Logic\u00a0100, 141\u2013187 (1999)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.2178\/jsl\/1190150152","volume":"67","author":"A. Blass","year":"2002","unstructured":"Blass, A., Gurevich, Y., Shelah, S.: On polynomial time computation over unordered structures. Journal of Symbolic Logic\u00a067, 1093\u20131125 (2002)","journal-title":"Journal of Symbolic Logic"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"Cai, J., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012, 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"Chandra, A., Harel, D.: Structure and complexity of relational queries. Journal of Computer and System Sciences\u00a025, 99\u2013128 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J.: A logic for PTIME and a parameterized halting problem. In: Proceedings of the 24th IEEE Symposium on Logic in Computer Science (2009)","DOI":"10.1109\/LICS.2009.11"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/logcom\/5.2.213","volume":"5","author":"A. Dawar","year":"1995","unstructured":"Dawar, A.: Generalized quantifiers and logical reducibilities. Journal of Logic and Computation\u00a05, 213\u2013226 (1995)","journal-title":"Journal of Logic and Computation"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Holm, B., Laubner, B.: Logics with rank operators. In: Proceedings of the 24th IEEE Symposium on Logic in Computer Science (2009)","DOI":"10.1109\/LICS.2009.24"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.entcs.2005.05.024","volume":"143","author":"A. Dawar","year":"2006","unstructured":"Dawar, A., Richerby, D., Rossman, B.: Choiceless polynomial time, counting and the Cai-F\u00fcrer-Immerman graphs (Extended abstract). Electronic Notes on Theoretical Compututer Science\u00a0143, 13\u201326 (2006)","journal-title":"Electronic Notes on Theoretical Compututer Science"},{"key":"4_CR9","unstructured":"Fagin, R.: Generalized first\u2013order spectra and polynomial\u2013time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation, SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-68804-8_3","volume-title":"Finite Model Theory and Its Applications, ch. 3","author":"E. Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E.: Finite Model Theory and Descriptive Complexity. In: Kolaitis, P.G., Libkin, L., Marx, M., Spencer, J., Vardi, M.Y., Venema, Y., Weinstein, S. (eds.) Finite Model Theory and Its Applications, ch. 3, pp. 125\u2013230. Springer, Heidelberg (2007)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proceedings of the 13th IEEE Symposium on Logic in Computer Science, pp. 6\u201315 (1998)","DOI":"10.1109\/LICS.1998.705639"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Definable tree decompositions. In: Proceedings of the 23rd IEEE Symposium on Logic in Computer Science, pp. 406\u2013417 (2008)","DOI":"10.1109\/LICS.2008.10"},{"key":"4_CR13","first-page":"91","volume":"36","author":"M. Grohe","year":"1999","unstructured":"Grohe, M., Ebbinghaus, H.-D.: Zur Struktur dessen, was wirklich berechenbar ist. Philosophia Naturalis\u00a036, 91\u2013116 (1999)","journal-title":"Philosophia Naturalis"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Mari\u00f1o, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"key":"4_CR15","first-page":"1","volume-title":"Current trends in theoretical computer science","author":"Y. Gurevich","year":"1988","unstructured":"Gurevich, Y.: Logic and the challenge of computer science. In: B\u00f6rger, E. (ed.) Current trends in theoretical computer science, pp. 1\u201357. Computer Science Press, Rockville (1988)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(89)90070-5","volume":"43","author":"L. Hella","year":"1989","unstructured":"Hella, L.: Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic\u00a043, 235\u2013271 (1989)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"422","DOI":"10.2307\/421173","volume":"2","author":"L. Hella","year":"1996","unstructured":"Hella, L., Kolaitis, P.G., Luosto, K.: Almost everywhere equivalence of logics in finite model theory. Bulletin of Symbolic Logic\u00a02, 422\u2013443 (1996)","journal-title":"Bulletin of Symbolic Logic"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"Immerman, N.: Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences\u00a025, 76\u201398 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Expressibility as a complexity measure: results and directions. In: Proceedings of the 2nd IEEE Symposium on Structure in Complexity Theory, pp. 194\u2013202 (1987)","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity theory retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.: Describing graphs: A first-order approach to graph canonization. In: Selman, A. (ed.) Complexity theory retrospective, pp. 59\u201381. Springer, Heidelberg (1990)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-540-30570-5_19","volume-title":"Database Theory - ICDT 2005","author":"A. Nash","year":"2004","unstructured":"Nash, A., Remmel, J.B., Vianu, V.: PTIME queries revisited. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 274\u2013288. Springer, Heidelberg (2004)"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(98)00314-4","volume":"224","author":"M. Otto","year":"1999","unstructured":"Otto, M.: Bisimulation-invariant PTIME and higher-dimensional \u03bc-calculus. Theoretical Computer Science\u00a0224, 237\u2013265 (1999)","journal-title":"Theoretical Computer Science"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proceedings of the 14th ACM Symposium on Theory of Computing, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04027-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T13:38:50Z","timestamp":1710596330000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04027-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642040269","9783642040276"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04027-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}