{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:20:34Z","timestamp":1775809234393,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540601784","type":"print"},{"value":"9783540447207","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_92","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:50Z","timestamp":1330278590000},"page":"313-366","source":"Crossref","is-referenced-by-count":13,"title":["Metafinite model theory"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Gurevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"17_CR1","unstructured":"S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases, Addison Wesley (1994)."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu, Generic Computation and Its Complexity, Proceedings of 23rd ACM Symposium on Theory of Computing (1991), 209\u2013219.","DOI":"10.1145\/103418.103444"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"L. Adleman and K. Manders, Computational complexity of decision problems for polynomials, Proceedings of 16th IEEE Symposium on Foundations of Computer Science (1975), 169\u2013177.","DOI":"10.1109\/SFCS.1975.9"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"L. Adleman and K. Manders, Diophantine Complexity, Proceedings of 17th IEEE Symposium on Foundations of Computer Science (1976), 81\u201388.","DOI":"10.1109\/SFCS.1976.13"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, Proceedings of 33rd IEEE Symposium on Foundations of Computer Science (1992), 210\u2013214.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"17_CR6","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, Journal of Symbolic Logic 42 (1977), 292\u2013296.","journal-title":"Journal of Symbolic Logic"},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc.21 (1989), 1\u201346.","journal-title":"Bull. Amer. Math. Soc."},{"key":"17_CR8","unstructured":"E. B\u00f6rger, Annotated Bibliography on Evolving Algebras, in: E. B\u00f6rger (Ed.), Specification and Validation Methods, Oxford University Press, to appear."},{"key":"17_CR9","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":"17_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"A. Chandra and D. Harel, Computable Queries for Relational Data Bases, Journal of Computer and System Sciences 21 (1980), 156\u2013178.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"K. Compton, 0-1 Laws in Logic and Combinatorics, in: NATO Adv. Study Inst. on Algorithms and Order, I. Rival (Ed.), 1988, 353\u2013383.","DOI":"10.1007\/978-94-009-2639-4_10"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0168-0072(87)90017-0","volume":"36","author":"K. Compton","year":"1987","unstructured":"K. Compton, C. Henson and S. Shelah, Nonconvergence, undecidability and intractability in asymptotic problems, Annals of Pure and Applied Logic 36 (1987), 207\u2013224.","journal-title":"Annals of Pure and Applied Logic"},{"key":"17_CR13","unstructured":"P. Crescenzi and V. Kann, A compendium of NP optimization problems, preprint (1995)."},{"key":"17_CR14","unstructured":"A. Dawar, Feasible Computation through Model Theory, PhD thesis, University of Pennsylvania (1993)."},{"key":"17_CR15","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, SIAM-AMS Proceedings 7 (1974), 43\u201373.","journal-title":"SIAM-AMS Proceedings"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del and K. Meer, Descriptive Complexity Theory over the Real Numbers, Proceedings of 27th ACM Sympposium on Theory of Computing (1995).","DOI":"10.1145\/225058.225151"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del and M. Otto, Inductive Definability with Counting on Finite Structures, in: Selected Papers, 6th Workshop on Computer Science Logic CSL 92, San Miniato 1992, Lecture Notes in Computer Science Nr. 702, Springer (1993), 231\u2013247.","DOI":"10.1007\/3-540-56992-8_15"},{"key":"17_CR18","volume-title":"Topological Graph Theory","author":"J. Gross","year":"1987","unstructured":"J. Gross and T. Tucker, Topological Graph Theory, Wiley, New York (1987)."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"S. Grumbach and J. Su, Finitely representable databases, Proceedings of 13th ACM Symposium on Principles of Database Systems (1994).","DOI":"10.1145\/182591.182654"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, Toward logic tailord for computational complexity, in: M. M. Richter et al. (Eds), Computation and Proof Theory, Springer Lecture Notes in Mathematics Nr. 1104 (1984), 175\u2013216.","DOI":"10.1007\/BFb0099486"},{"key":"17_CR21","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":"17_CR22","unstructured":"Y. Gurevich, Evolving Algebras 1993: Lipari Guide, in: E. B\u00f6rger (Ed.), Specification and Validation Methods, Oxford University Press, to appear."},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich and S. Shelah, Fixed Point Extensions of First Order Logic, Annals of Pure and Applied Logic 32 (1986), 265\u2013280.","journal-title":"Annals of Pure and Applied Logic"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"T. Hirst and D. Harel, Completeness Results for Recursive Databases, Journal of Computer and System Sciences, to appear. (Also: 12th ACM Symp. on Principles of Database Systems (1993), 244\u2013252.)","DOI":"10.1145\/153850.153905"},{"key":"17_CR25","unstructured":"T. Hirst and D. Harel, More about Recursive Structures: Zero-One Laws and Expressibility vs. Complexity, unpublished (1995)."},{"key":"17_CR26","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/0022-0000(83)90048-X","volume":"27","author":"B. Hodgson","year":"1983","unstructured":"B. Hodgson and C. Kent, A Normal form for Arithmetical Representation of NP-sets, Journal of Computer and System Sciences 27 (1983), 378\u2013388.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR27","doi-asserted-by":"crossref","first-page":"86","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, Journal of Computer and Systems Sciences 25 (1982), 86\u2013104.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"17_CR28","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational Queries Computable in Polynomial Time, Information and Control 68 (1986), 86\u2013104.","journal-title":"Information and Control"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"N. Immerman, Expressibility as a Complexity Measure: Results and Directions, Proc. of 2nd Conf. on Structure in Complexity Theory (1987), 194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"17_CR30","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":"17_CR31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"N. Immerman and E. Lander, Describing Graphs: A First Order Approach to Graph Canonization, in: A. Selman (Ed), Complexity Theory Retrospective. (In Honor of Juris Hartmanis), Springer, New York 1990, 59\u201381."},{"key":"17_CR32","doi-asserted-by":"crossref","first-page":"818","DOI":"10.2307\/2274135","volume":"49","author":"J. Jones","year":"1984","unstructured":"J. Jones and Y. Matijasevich, Register machine proof of the theorem of exponential diophantine representation of enumerable sets, Journal of Symbolic Logic 49 (1984), 818\u2013829.","journal-title":"Journal of Symbolic Logic"},{"key":"17_CR33","doi-asserted-by":"crossref","unstructured":"F. Kabanza, J. Stevenne and P. Wolper, Handling Infinite Temporal Data, to appear in Journal of Computer and System Sciences. A preliminary version appeared in Proceedings of 9th ACM Syposium on Principles of Database Systems (1990).","DOI":"10.1145\/298514.298590"},{"key":"17_CR34","first-page":"1073","volume-title":"Handbook of Theoretical Computer Science, vol. B","author":"P. Kanellakis","year":"1990","unstructured":"P. Kanellakis, 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":"17_CR35","doi-asserted-by":"crossref","unstructured":"P. Kanellakis, G. Kuper and P. Revesz, Constraint Query Languages, Proceedings of 9th ACM Symposium on Principles of Database Systems (1990), 299\u2013313.","DOI":"10.1145\/298514.298582"},{"key":"17_CR36","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(82)90076-7","volume":"12","author":"C. Kent","year":"1982","unstructured":"C. Kent and B. Hodgson, An arithmetical characterization of NP, Theoretical Computer Science 12 (1982), 255\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"17_CR37","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0003-4843(80)90014-5","volume":"18","author":"J. Lynch","year":"1980","unstructured":"J. Lynch, Almost sure theories, Annals of Mathematical Logic 18 (1980), 91\u2013135.","journal-title":"Annals of Mathematical Logic"},{"key":"17_CR38","volume-title":"Hilbert's Tenth Problem","author":"Y. Matijasevich","year":"1993","unstructured":"Y. Matijasevich, Hilbert's Tenth Problem, MIT Press, Cambridge (1993)."},{"key":"17_CR39","doi-asserted-by":"crossref","unstructured":"M. Otto, Generalized Quantifiers for Simple Properties, Proceedings of IEEE Symposium on Logic in Computer Science (1994), 30\u201339.","DOI":"10.1109\/LICS.1994.316089"},{"key":"17_CR40","doi-asserted-by":"crossref","unstructured":"M. Otto, The Expressive Power of Fixed-Point Logic with Counting, Journal of Symbolic Logic, to appear.","DOI":"10.2307\/2275602"},{"key":"17_CR41","unstructured":"M. Otto, Habilitationsschrift, RWTH Aachen 1995."},{"key":"17_CR42","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Optimization, approximization and complexity classes, Journal of Computer and System Sciences 43 (1991), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR43","doi-asserted-by":"crossref","first-page":"641","DOI":"10.2307\/2273594","volume":"47","author":"B. Poizat","year":"1982","unstructured":"B. Poizat, Deux ou trois choses que je sais de Ln, Journal of Symbolic Logic 47 (1982), 641\u2013658.","journal-title":"Journal of Symbolic Logic"},{"key":"17_CR44","unstructured":"S. Shelah, The very weak zero-one law for random graphs with order and random binary functions, preprint (1994)."},{"key":"17_CR45","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF00383198","volume":"7","author":"J. Spencer","year":"1991","unstructured":"J. Spencer, Nonconvergence in the theory of random orders, Order 7 (1991), 341\u2013348.","journal-title":"Order"},{"key":"17_CR46","unstructured":"J. Tyszkiewicz, private communication."},{"key":"17_CR47","unstructured":"J. D. Ullman, Database and Knowledge-Base Systems, Vol. I and II, Computer Science Press (1989)."},{"key":"17_CR48","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of Relational Query Languages, Proc. of 14th Symposium on Theory of Computing (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_92.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:55:42Z","timestamp":1742597742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_92"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_92","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}