{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:31Z","timestamp":1725663631201},"publisher-location":"Berlin, Heidelberg","reference-count":94,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540535072"},{"type":"electronic","value":"9783540466826"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-53507-1_67","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:08:45Z","timestamp":1330189725000},"page":"1-24","source":"Crossref","is-referenced-by-count":9,"title":["Finite-model theory\u2014a personal perspective"],"prefix":"10.1007","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"issue":"1","key":"1_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic, 55(1):113\u2013150, March 1990.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"M. Ajtai and Y. Gurevich. Monotone versus positive. Journal of the ACM, 34:1004\u20131015, 1987.","journal-title":"Journal of the ACM"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and Y. Gurevich. Datalog vs. first-order logic. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 142\u2013146, 1989.","DOI":"10.1109\/SFCS.1989.63469"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u03a3 1 1 -formulae on finite structures. Annals of Pure and Applied Logic, 24:1\u201348, 1983.","journal-title":"Annals of Pure and Applied Logic"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1002\/malq.19550010403","volume":"1","author":"G. Asser","year":"1955","unstructured":"G. Asser. Das Repr\u00e4sentantenproblem im Pr\u00e4dikatenkalk\u00fcl der ersten Stufe mit identit\u00e4t. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 1:252\u2013263, 1955.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"J. Barwise. Model-theoretic logics: background and aims. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 3\u201323. Springer-Verlag, 1985.","DOI":"10.1017\/9781316717158.004"},{"key":"1_CR7","unstructured":"J. H. Bennett. On spectra. PhD thesis, Princeton University, 1962."},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/S0019-9958(85)80027-9","volume":"67","author":"A. Blass","year":"1985","unstructured":"A. Blass, Y. Gurevich, and D. Kozen. A zero-one law for logic with a fixed point operator. Information and Control, 67:70\u201390, 1985.","journal-title":"Information and Control"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/0211048","volume":"11","author":"R. Book","year":"1982","unstructured":"R. Book, C. Wilson, and X. Mei-Rui. Relativizing time, space, and time-space. SIAM Journal on Computing, 11:571\u2013581, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR10","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. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 612\u2013617, 1989.","DOI":"10.1109\/SFCS.1989.63543"},{"key":"1_CR11","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences, 25:99\u2013128, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"A. Chandra. Theory of database queries. In Proc. 7th ACM Symp. on Principles of Database Systems, pages 1\u20139, 1988.","DOI":"10.1145\/308386.308396"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0168-0072(87)90017-0","volume":"36","author":"K. J. Compton","year":"1987","unstructured":"K. J. Compton, C. W. Henson, and S. Shelah. Nonconvergence, undecidability, and intractibility in asymptotic problems. Annals of Pure and Applied Logic, 36:207\u2013224, 1987.","journal-title":"Annals of Pure and Applied Logic"},{"key":"1_CR14","unstructured":"A. Church. Introduction to mathematical logic, volume I. Princeton University Press, 1956."},{"key":"1_CR15","unstructured":"C. C. Chang and H. J. Keisler. Model Theory. North-Holland, 1973."},{"key":"1_CR16","unstructured":"A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Science, pages 24\u201330. North Holland, 1964."},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0001-8708(87)90019-3","volume":"65","author":"K. J. Compton","year":"1987","unstructured":"K. J. Compton. A logical approach to asymptotic combinatorics I: First-order properties. Advances in Mathematics, 65:65\u201396, 1987.","journal-title":"Advances in Mathematics"},{"key":"1_CR18","unstructured":"K. Compton. 0\u20131 laws in logic and combinatorics. In I. Rival, editor, Proc. 1987 NATO Adv. Study Inst. on algorithms and order, pages 353\u2013383. Reidel, 1988."},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem proving procedures. In Proc. 3rd ACM Symp. on Theory of Computing, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"S. A. Cook. A hierarchy for nondeterministic time complexity. In Proc. 4th ACM Symp. on Theory of Computing, pages 187\u2013192, 1972.","DOI":"10.1145\/800152.804913"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"M. I. Dekhtyar. On the relativization of deterministic and nondeterministic complexity classes. In Proc. 5th Conference on Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science 5, pages 255\u2013259, 1976.","DOI":"10.1007\/3-540-07854-1_183"},{"key":"1_CR22","unstructured":"D. Dreben and W. D. Goldfarb. The Decision Problem: Solvable Classes of Quantificational Formulas. Addison-Wesley, 1979."},{"key":"1_CR23","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, trees, and flowers. Canadian J. Math., 17:449\u2013467, 1965.","journal-title":"Canadian J. Math."},{"key":"1_CR24","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:129\u2013141, 1961.","journal-title":"Fund. Math."},{"key":"1_CR25","unstructured":"H. B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972."},{"key":"1_CR26","unstructured":"P. Erd\u00f6s and J. Spencer. Probabilistic methods in combinatorial mathematics. Akadamia Kiado, 1974."},{"key":"1_CR27","unstructured":"R. Fagin. Probabilities on finite models. Notices of the American Mathematical Society, page A714, October 1972. Abstract number 72T-E90."},{"key":"1_CR28","unstructured":"R. Fagin. Contributions to the model theory of finite structures. PhD thesis, University of California at Berkeley, 1973."},{"key":"1_CR29","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43\u201373, 1974.","journal-title":"Complexity of Computation, SIAM-AMS Proceedings"},{"key":"1_CR30","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 Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"1_CR31","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. A spectrum hierarchy. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:123\u2013134, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/malq.19750210116","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. A two-cardinal characterization of double spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:121\u2013122, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"issue":"1","key":"1_CR33","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1017\/S0022481200051756","volume":"41","author":"R. Fagin","year":"1976","unstructured":"R. Fagin. Probabilities on finite models. Journal of Symbolic Logic, 41(1):50\u201358, March 1976.","journal-title":"Journal of Symbolic Logic"},{"issue":"4","key":"1_CR34","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1145\/322344.322347","volume":"29","author":"R. Fagin","year":"1982","unstructured":"R. Fagin. Horn clauses and database dependencies. Journal of the ACM, 29(4):952\u2013985, October 1982.","journal-title":"Journal of the ACM"},{"key":"1_CR35","unstructured":"R. Fra\u00efss\u00e9. Sur les classifications des systems de relations. Publications Sc. d l'Universit\u00e9 d'Alger, 1(I), 1954."},{"key":"1_CR36","unstructured":"R. Fra\u00efss\u00e9. Cours de Logique Mathematique. Gauthier-Villars and E. Nauwelaerts, 1967. English translation is Course in Mathematical Logic, Reidel Holland, 1973, translated by D. Louvish."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy. In Proc. 22nd IEEE Symp. on Foundations of Computer Science, pages 260\u2013270, 1981.","DOI":"10.1109\/SFCS.1981.35"},{"key":"1_CR38","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1090\/psapm\/034\/846853","volume":"34","author":"R. Fagin","year":"1986","unstructured":"R. Fagin and M. Y. Vardi. The theory of data dependencies: a survey. In Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics, volume 34, pages 19\u201372. American Mathematical Society, 1986.","journal-title":"Mathematics of Information Processing, Proceedings of Symposia in Applied Mathematics"},{"key":"1_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02759729","volume":"2","author":"H. Gaifman","year":"1964","unstructured":"H. Gaifman. Concerning measures in first-order calculi. Israel Journal of Mathematics, 2:1\u201318, 1964.","journal-title":"Israel Journal of Mathematics"},{"key":"1_CR40","unstructured":"M. Garey and D. S. Johnson. Computers and intractibility: a guide to the theory of NP-completeness. Freeman, 1979."},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. S. Johnson, and L. J. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237\u2013267, 1976.","journal-title":"Theoretical Computer Science"},{"key":"1_CR42","first-page":"17","volume":"2","author":"Y. V. Glebskis","year":"1969","unstructured":"Y. V. Glebskis, D. I. Kogan, M. I. Liogon'kis, and V. A. Talanov. Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika, 2:17\u201328, 1969.","journal-title":"Kibernetika"},{"key":"1_CR43","unstructured":"H. Gaifman, H. Mairson, Y. Sagiv, and M. Y. Vardi. Undecidable optimization problems for database logic programs. In Proc. 2nd IEEE Symp. on Logic in Computer Science, pages 106\u2013115, 1987."},{"key":"1_CR44","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/S0273-0979-1984-15207-8","volume":"10","author":"W. D. Goldfarb","year":"1984","unstructured":"W. D. Goldfarb. The G\u00f6del class with equality is unsolvable. Bull. Amer. Math. Soc. (New Series), 10:113\u2013115, 1984.","journal-title":"Bull. Amer. Math. Soc. (New Series)"},{"key":"1_CR45","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/S0019-9958(83)80043-6","volume":"52","author":"E. Grandjean","year":"1983","unstructured":"E. Grandjean. Complexity of the first-order theory of almost all structures. Information and Control, 52:180\u2013204, 1983.","journal-title":"Information and Control"},{"key":"1_CR46","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:265\u2013280, 1986.","journal-title":"Annals of Pure and Applied Logic"},{"key":"1_CR47","unstructured":"Y. Gurevich and S. Shelah. A preservation theorem in finite model theory. To appear, 1990."},{"key":"1_CR48","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1017\/S0022481200051513","volume":"41","author":"Y. Gurevich","year":"1976","unstructured":"Y. Gurevich. The decision problem for standard classes. Journal of Symbolic Logic, 41:460\u2013464, 1976.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR49","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Toward logic tailored for computational complexity. In M. Richter et al., editor, Computation and Proof Theory, pages 175\u2013216. Springer Lecture Notes in Math. 1104, 1984.","DOI":"10.1007\/BFb0099486"},{"key":"1_CR50","unstructured":"Y. Gurevich. Logic and the challenge of computer science. In E. B\u00f6rger, editor, Current trends in theoretical computer science, pages 1\u201357. Computer Science Press, 1988."},{"key":"1_CR51","unstructured":"Y. Gurevich. On finite model theory. In S. R. Buss and P. J. Scott, editors, Perspectives in Computer Science. Birkhauser, 1990. Proceedings of Feasible Mathematics Workshop, Cornell University, June 1989."},{"key":"1_CR52","first-page":"43","volume":"26","author":"H. Gaifman","year":"1985","unstructured":"H. Gaifman and M. Y. Vardi. A simple proof that connectivity is not first-order. Bulletin of the European Association for Theoretical Computer Science, 26:43\u201345, June 1985.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, and J. Sewelson. Sparse sets in NP-P \u2014 EXPTIME vs. NEXPTIME. Information and Control, 65:159\u2013181, 1985.","journal-title":"Information and Control"},{"key":"1_CR54","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"N. Immerman. Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences, 22:384\u2013406, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR55","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences, 25:76\u201398, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR56","doi-asserted-by":"crossref","first-page":"76","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:76\u201398, 1986.","journal-title":"Information and Control"},{"issue":"4","key":"1_CR57","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 Journal on Computing, 16(4):760\u2013778, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR58","doi-asserted-by":"crossref","unstructured":"N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, pages 935\u2013938, 1988.","DOI":"10.1137\/0217058"},{"key":"1_CR59","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/038\/1020810","volume":"38","author":"N. Immerman","year":"1989","unstructured":"N. Immerman. Descriptive and computational complexity. In J. Hartmanis, editor, Computational Complexity Theory, Proc. Symp. in Applied Math. 38, pages 75\u201391. American Mathematical Society, 1989.","journal-title":"Computational Complexity Theory, Proc. Symp. in Applied Math."},{"key":"1_CR60","doi-asserted-by":"crossref","unstructured":"N. D. Jones and A. L. Selman. Turing machines and the spectra of first-order formulas with equality. Journal of Symbolic Logic, pages 139\u2013150, 1974.","DOI":"10.2307\/2272354"},{"key":"1_CR61","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis. Elements of relational database theory. In A. R. Meyer, M. Nivat, M. S. Paterson, D. Perrin, and J. van Leeuwen, editors, The handbook of theoretical computer science. North Holland, 1990. Also available as Brown University Technical Report CS-89-39, 1989.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"1_CR62","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, 1975.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1_CR63","unstructured":"M. Kaufmann. Counterexample to the 0\u20131 law for existential monadic second-order logic. CLI Internal Note 32, Computational Logic Inc., December 1987."},{"key":"1_CR64","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis. Implicit definability on finite structures and unambiguous computations. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 168\u2013180, 1990.","DOI":"10.1109\/LICS.1990.113743"},{"key":"1_CR65","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0012-365X(85)90112-8","volume":"54","author":"M. Kaufmann","year":"1985","unstructured":"M. Kaufmann and S. Shelah. On random models of finite power and monadic logic. Discrete Mathematics, 54:285\u2013293, 1985.","journal-title":"Discrete Mathematics"},{"key":"1_CR66","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. The decision problem for the probabilities of higher-order properties. In Proc. 19th ACM Symp. on Theory of Computing, pages 425\u2013435, 1987.","DOI":"10.1145\/28395.28441"},{"key":"1_CR67","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/0890-5401(90)90065-P","volume":"87","author":"P. G. Kolaitis","year":"1990","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. 0\u20131 laws and decision problems for fragments of second-order logic. Information and Computation, 87:302\u2013338, 1990.","journal-title":"Information and Computation"},{"key":"1_CR68","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. 0\u20131 laws for fragments of second-order logic. Research Report RJ 7508, IBM, 1990.","DOI":"10.1016\/0890-5401(90)90065-P"},{"key":"1_CR69","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. 0\u20131 laws for infinitary logics. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 156\u2013167, 1990.","DOI":"10.1109\/LICS.1990.113742"},{"key":"1_CR70","first-page":"115","volume":"9","author":"L. A. Levin","year":"1973","unstructured":"L. A. Levin. Universal sorting problems. Problemy Peredaci Informacii, 9:115\u2013116, 1973. In Russian. English translation in Problems of Information Transmission 9:265\u2013266.","journal-title":"Problemy Peredaci Informacii"},{"key":"1_CR71","unstructured":"H. R. Lewis. Unsolvable Classes of Quantificational Formulas. Addison-Wesley, 1979."},{"key":"1_CR72","first-page":"17","volume":"4","author":"A. B. Livchak","year":"1982","unstructured":"A. B. Livchak. The relational model for systems of automatic testing. Automatic documentation and mathematical linguistics, 4:17\u201319, 1982.","journal-title":"Automatic documentation and mathematical linguistics"},{"key":"1_CR73","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:91\u2013135, 1980.","journal-title":"Annals of Mathematical Logic"},{"key":"1_CR74","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1090\/S0002-9947-1985-0768725-2","volume":"287","author":"J. Lynch","year":"1985","unstructured":"J. Lynch. Probabilities of first-order sentences about unary functions. Trans. American Mathematical Society, 287:543\u2013568, 1985.","journal-title":"Trans. American Mathematical Society"},{"key":"1_CR75","unstructured":"D. Maier. The theory of relational databases. Computer Science Press, 1983."},{"key":"1_CR76","doi-asserted-by":"crossref","unstructured":"J. A. Makowsky. Compactness, embeddings and definability. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 645\u2013716. Springer-Verlag, 1985.","DOI":"10.1017\/9781316717158.026"},{"key":"1_CR77","doi-asserted-by":"crossref","unstructured":"L. Pacholski and W. Szwast. The 0\u20131 law fails for the class of existential second-order G\u00f6del sentences with equality. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 160\u2013163, 1989.","DOI":"10.1109\/SFCS.1989.63472"},{"key":"1_CR78","doi-asserted-by":"crossref","first-page":"331","DOI":"10.4064\/aa-9-4-331-340","volume":"9","author":"R. Rado","year":"1964","unstructured":"R. Rado. Universal graphs and universal functions. Acta Arith., 9:331\u2013340, 1964.","journal-title":"Acta Arith."},{"key":"1_CR79","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4:177\u2013192, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR80","doi-asserted-by":"crossref","first-page":"160","DOI":"10.2307\/2266243","volume":"17","author":"H. Scholz","year":"1952","unstructured":"H. Scholz. Problem #1. Journal of Symbolic Logic, 17:160, 1952.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR81","unstructured":"S. Shelah. Classification theory and the number of non-isomorphic models. North Holland, 1978."},{"key":"1_CR82","unstructured":"J. R. Shoenfield. Mathematical Logic. Addison-Wesley, 1967."},{"key":"1_CR83","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/S0894-0347-1988-0924703-8","volume":"1","author":"S. Shelah","year":"1988","unstructured":"S. Shelah and J. Spencer. Zero-one laws for sparse random graphs. Journal of the American Mathematical Society, 1:97\u2013115, 1988.","journal-title":"Journal of the American Mathematical Society"},{"key":"1_CR84","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:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"1_CR85","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2307\/2964569","volume":"24","author":"W. W. Tait","year":"1959","unstructured":"W. W. Tait. A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic, 24:15\u201316, 1959.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR86","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1016\/S1385-7258(54)50074-0","volume":"16","author":"A. Tarski","year":"1954","unstructured":"A. Tarski. Contributions to the theory of models I,II. Indagationes Mathematicae, 16:572\u2013588, 1954.","journal-title":"Indagationes Mathematicae"},{"key":"1_CR87","unstructured":"V. A. Talanov and V. V. Knyazev. The asymptotic truth value of infinite formulas. In Proc. All-Union seminar on discrete mathematics and its applications, pages 56\u201361, 1984. See Math. Rev. 89g:03054."},{"key":"1_CR88","first-page":"569","volume":"70","author":"B. A. Trakhtenbrot","year":"1950","unstructured":"B. A. Trakhtenbrot. Impossibility of an algorithm for the decision problem in finite classes. Doklady Akademii Nauk SSSR, 70:569\u2013572, 1950.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"1_CR89","unstructured":"J. D. Ullman. Database and Knowledge-Base Systems, Volumes I and II. Computer Science Press, 1989."},{"key":"1_CR90","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. In Proc. 14th ACM Symp. on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"1_CR91","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. On decomposition of relational databases. In Proc. 23rd IEEE Symp. on Foundations of Computer Science, pages 176\u2013185, 1982.","DOI":"10.1109\/SFCS.1982.75"},{"key":"1_CR92","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/S1385-7258(54)50058-2","volume":"16","author":"R. L. Vaught","year":"1954","unstructured":"R. L. Vaught. Applications of the Lowenheim-Skolem-Tarski theorem to problems of completeness and decidability. Indagationes Mathematicae, 16:467\u2013472, 1954.","journal-title":"Indagationes Mathematicae"},{"issue":"1","key":"1_CR93","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2307\/2964336","volume":"25","author":"R. L. Vaught","year":"1960","unstructured":"R. L. Vaught. Sentences true in all constructive models. Journal of Symbolic Logic, 25(1):39\u201353, March 1960.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR94","unstructured":"C. Wilson. Relativization, reducibilities, and the exponential hierarchy. Master's thesis, Toronto, 1980."}],"container-title":["Lecture Notes in Computer Science","ICDT '90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-53507-1_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:50:32Z","timestamp":1605628232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-53507-1_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540535072","9783540466826"],"references-count":94,"URL":"https:\/\/doi.org\/10.1007\/3-540-53507-1_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}