{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T09:59:39Z","timestamp":1760954379237},"reference-count":104,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1993,8,1]],"date-time":"1993-08-01T00:00:00Z","timestamp":744163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7290,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1993,8]]},"DOI":"10.1016\/0304-3975(93)90218-i","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:47:37Z","timestamp":1027655257000},"page":"3-31","source":"Crossref","is-referenced-by-count":65,"title":["Finite-model theory - a personal perspective"],"prefix":"10.1016","volume":"116","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(93)90218-I_BIB1","first-page":"110","article-title":"Universality of data retrieval languages","author":"Aho","year":"1979","journal-title":"Proc. 6th ACM Symp. on Principles of Programming Languages"},{"key":"10.1016\/0304-3975(93)90218-I_BIB2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"10.1016\/0304-3975(93)90218-I_BIB3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","article-title":"Reachability is harder for directed than for undirected finite graphs","volume":"55","author":"Ajtai","year":"1990","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB4","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1145\/31846.31852","article-title":"Monotone versus positive","volume":"34","author":"Ajtai","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(93)90218-I_BIB5","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1109\/SFCS.1989.63469","article-title":"DATALOG vs. first-order logic","author":"Ajtai","year":"1989","journal-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB6","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1002\/malq.19550010403","article-title":"Das Repr\u00e4sentantenproblem im Pr\u00e4dikatenkalk\u00fcl der ersten Stufe mit identit\u00e4t","volume":"1","author":"Asser","year":"1955","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB7","series-title":"Model-Theoretic Logics","first-page":"3","article-title":"Model-theoretic logics: background and aims","author":"Barwise","year":"1985"},{"key":"10.1016\/0304-3975(93)90218-I_BIB8","series-title":"Ph.D. Thesis","article-title":"On spectra","author":"Bennett","year":"1962"},{"key":"10.1016\/0304-3975(93)90218-I_BIB9","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/S0019-9958(85)80027-9","article-title":"A zero-one law for logic with a fixed point operator","volume":"67","author":"Blass","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(93)90218-I_BIB10","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/0211048","article-title":"Relativizing time, space, and time-space","volume":"11","author":"Book","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(93)90218-I_BIB11","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1109\/SFCS.1989.63543","article-title":"An optimal lower bound on the number of variables for graph identification","author":"Cai","year":"1989","journal-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB12","first-page":"1","article-title":"Theory of database queries","author":"Chandra","year":"1988","journal-title":"Proc. 7th ACM Symp. on Principles of Database Systems"},{"key":"10.1016\/0304-3975(93)90218-I_BIB13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","article-title":"Structure and complexity of relational queries","volume":"25","author":"Chandra","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB14","series-title":"Model Theory","author":"Chang","year":"1990"},{"key":"10.1016\/0304-3975(93)90218-I_BIB15","volume":"Vol. I","author":"Church","year":"1956"},{"key":"10.1016\/0304-3975(93)90218-I_BIB16","series-title":"Proc. 1964 Internat. Cong. for Logic, Methodology, and Philosophy of Science","first-page":"24","article-title":"The intrinsic computational difficulty of functions","author":"Cobham","year":"1964"},{"key":"10.1016\/0304-3975(93)90218-I_BIB17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0001-8708(87)90019-3","article-title":"A logical approach to asymptotic combinatorics I: first-order properties","volume":"65","author":"Compton","year":"1987","journal-title":"Adv. in Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB18","series-title":"Proc. 1987 NATO Adv. Study Inst. on Algorithms and Order","article-title":"0\u20131 laws in logic and combinatorics","author":"Compton","year":"1988"},{"key":"10.1016\/0304-3975(93)90218-I_BIB19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0168-0072(87)90017-0","article-title":"Noncovergence, undecidability, and intractability in asymptotic problems","volume":"36","author":"Compton","year":"1987","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB20","first-page":"151","article-title":"The complexity of theorem proving procedures","author":"Cook","year":"1971","journal-title":"Proc. 3rd ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(93)90218-I_BIB21","first-page":"187","article-title":"A hierarchy for nondeterministic time complexity","author":"Cook","year":"1972","journal-title":"Proc. 4th ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(93)90218-I_BIB22","series-title":"Proc. 5th Conf. on Mathematical Foundations of Computer Science","first-page":"255","article-title":"On the relativization of deterministic and nondeterministic complexity classes","volume":"Vol. 45","author":"Dekhtyar","year":"1976"},{"key":"10.1016\/0304-3975(93)90218-I_BIB23","series-title":"The Decision Problem: Solvable Classes of Quantificational Formulas","author":"Dreben","year":"1979"},{"key":"10.1016\/0304-3975(93)90218-I_BIB24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Canad. J. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","article-title":"An application of games to the completeness problem for formalized theories","volume":"49","author":"Ehrenfeucht","year":"1961","journal-title":"Fund. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB26","series-title":"A Mathematical Introduction to Logic","author":"Enderton","year":"1972"},{"key":"10.1016\/0304-3975(93)90218-I_BIB27","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01895716","article-title":"Asymmetric graphs","volume":"14","author":"Erd\u00f6s","year":"1963","journal-title":"Acta Math. Acad. Sci. Hung. Acad. Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB28","series-title":"Probabilistic Methods in Combinatorics","author":"Erd\u00f6s","year":"1974"},{"key":"10.1016\/0304-3975(93)90218-I_BIB29","first-page":"A714","article-title":"Probabilities on finite models","author":"Fagin","year":"1972","journal-title":"Notices Amer. Math. Soc."},{"key":"10.1016\/0304-3975(93)90218-I_BIB30","series-title":"Ph.D. Thesis","article-title":"Contributions to the model theory of finite structures","author":"Fagin","year":"1973"},{"key":"10.1016\/0304-3975(93)90218-I_BIB31","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin","year":"1974"},{"key":"10.1016\/0304-3975(93)90218-I_BIB32","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","article-title":"Monadic generalized spectra","volume":"21","author":"Fagin","year":"1975","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB33","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","article-title":"A spectrum hierarchy","volume":"21","author":"Fagin","year":"1975","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB34","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/malq.19750210116","article-title":"A two-cardinal characterization of double spectra","volume":"21","author":"Fagin","year":"1975","journal-title":"Z. Math. Logik Grundlag. Math."},{"issue":"1","key":"10.1016\/0304-3975(93)90218-I_BIB35","doi-asserted-by":"crossref","first-page":"50","DOI":"10.2307\/2272945","article-title":"Probabilities on finite models","volume":"41","author":"Fagin","year":"1976","journal-title":"J. Symbolic Logic"},{"issue":"4","key":"10.1016\/0304-3975(93)90218-I_BIB36","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1145\/322344.322347","article-title":"Horn clauses and database dependencies","volume":"29","author":"Fagin","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(93)90218-I_BIB37","article-title":"On monadic NP vs. monadic co-NP","author":"Fagin","year":"1993","journal-title":"IBM Research Report"},{"key":"10.1016\/0304-3975(93)90218-I_BIB38","first-page":"19","article-title":"The theory of data dependencies: a survey","volume":"Vol. 34","author":"Fagin","year":"1986"},{"issue":"I","key":"10.1016\/0304-3975(93)90218-I_BIB39","first-page":"135","article-title":"Sur quelques classifications des systems de relations","volume":"1","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Publ. Sc. d l'Universit\u00e9 d'Alger"},{"key":"10.1016\/0304-3975(93)90218-I_BIB40_1","series-title":"Cours de Logique Mathematique","author":"Fra\u00efss\u00e9","year":"1967"},{"key":"10.1016\/0304-3975(93)90218-I_BIB40_2","series-title":"Course in Mathematical Logic","author":"Fra\u00efss\u00e9","year":"1973"},{"key":"10.1016\/0304-3975(93)90218-I_BIB41","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/SFCS.1981.35","article-title":"Parity, circuits, and the polynomial time hierarchy","author":"Furst","year":"1981","journal-title":"Proc. 22nd IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02759729","article-title":"Concerning measures in first-order calculi","volume":"2","author":"Gaifman","year":"1964","journal-title":"Israel J. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB43","first-page":"106","article-title":"Undecidable optimization problems for database logic programs","author":"Gaifman","year":"1987","journal-title":"Proc. 2nd IEEE Symp. on Logic in Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB44","first-page":"43","article-title":"A simple proof that connectivity is not first-order","volume":"26","author":"Gaifman","year":"1985","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB45","series-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/0304-3975(93)90218-I_BIB46","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB47","first-page":"17","article-title":"Range and degree of realizability of formulas in the restricted predicate calculus","volume":"2","author":"Glebski\u01d0","year":"1969","journal-title":"Kibernetika"},{"key":"10.1016\/0304-3975(93)90218-I_BIB48","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/S0273-0979-1984-15207-8","article-title":"The G\u00f6del class with equality is unsolvable","volume":"10","author":"Goldfarb","year":"1984","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"10.1016\/0304-3975(93)90218-I_BIB49","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/S0019-9958(83)80043-6","article-title":"Complexity of the first-order theory of almost all structures","volume":"52","author":"Grandjean","year":"1983","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(93)90218-I_BIB50","doi-asserted-by":"crossref","first-page":"460","DOI":"10.2307\/2272244","article-title":"The decision problem for standard classes","volume":"41","author":"Gurevich","year":"1976","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB51","series-title":"Computation and Proof Theory","first-page":"175","article-title":"Toward logic tailored for computational complexity","volume":"Vol. 1104","author":"Gurevich","year":"1984"},{"key":"10.1016\/0304-3975(93)90218-I_BIB52","series-title":"Current Trends in Theoretical Computer Science","first-page":"1","article-title":"Logic and the challenge of computer science","author":"Gurevich","year":"1988"},{"key":"10.1016\/0304-3975(93)90218-I_BIB53_1","series-title":"Perspectives in Computer Science","article-title":"On finite model theory","author":"Gurevich","year":"1990"},{"key":"10.1016\/0304-3975(93)90218-I_BIB53_2","series-title":"Proc. of Feasible Mathematics Workshop","article-title":"On finite model theory","author":"Gurevich","year":"1989"},{"key":"10.1016\/0304-3975(93)90218-I_BIB54","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","article-title":"Fixed-point extensions of first-order logic","volume":"32","author":"Gurevich","year":"1986","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB55","series-title":"Proc. 4th Conf. on Mathematical Foundations of Computer Science","first-page":"30","article-title":"On logics of discovery","volume":"Vol. 32","author":"H\u00e1jek","year":"1975"},{"issue":"1","key":"10.1016\/0304-3975(93)90218-I_BIB56","first-page":"91","article-title":"Generalized quantifiers and finite sets","volume":"14","author":"H\u00e1jek","year":"1977","journal-title":"Prace Nauk. Inst. Mat. Politech. Wroclaw Ser. Konfer."},{"key":"10.1016\/0304-3975(93)90218-I_BIB57","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","article-title":"Sparse sets in NP-P\u2014EXPTIME vs. NEXPTIME","volume":"65","author":"Hartmanis","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(93)90218-I_BIB58","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","article-title":"Number of quantifiers is better than number of tape cells","volume":"22","author":"Immerman","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB59","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","article-title":"Upper and lower bounds for first-order expressibility","volume":"25","author":"Immerman","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB60","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","volume":"68","author":"Immerman","year":"1986","journal-title":"Inform. and Control"},{"issue":"4","key":"10.1016\/0304-3975(93)90218-I_BIB61","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/0304-3975(93)90218-I_BIB62","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","article-title":"Nondeterministic space is closed under complement","volume":"17","author":"Immerman","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(93)90218-I_BIB63","first-page":"75","article-title":"Descriptive and computational complexity","volume":"Vol. 38","author":"Immerman","year":"1989"},{"key":"10.1016\/0304-3975(93)90218-I_BIB65","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","article-title":"Turing machines and the spectra of first-order formulas with equality","volume":"39","author":"Jones","year":"1974","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB66","doi-asserted-by":"crossref","first-page":"137","DOI":"10.7146\/math.scand.a-10468","article-title":"Universal relational systems","volume":"4","author":"J\u00f3nsson","year":"1956","journal-title":"Math. Scand."},{"key":"10.1016\/0304-3975(93)90218-I_BIB67","series-title":"The Handbook of Theoretical Computer Science","article-title":"Elements of relational database theory","author":"Kanellakis","year":"1990"},{"key":"10.1016\/0304-3975(93)90218-I_BIB68","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1975"},{"key":"10.1016\/0304-3975(93)90218-I_BIB69","unstructured":"M. Kaufmann, Counterexample to the 0\u20131 law for existential monadic second-order logic, CLI Internal Note 32, Computational Logic Inc., 1987."},{"key":"10.1016\/0304-3975(93)90218-I_BIB70","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0012-365X(85)90112-8","article-title":"On random models of finite power and monadic logic","volume":"54","author":"Kaufmann","year":"1985","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB71","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1109\/LICS.1990.113743","article-title":"Implicit definability on finite structures and unambiguous computations","author":"Kolaitis","year":"1990","journal-title":"Proc. 5th IEEE Symp. on Logic in Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB72","first-page":"425","article-title":"The decision problems for the probabilities of higher-order properties","author":"Kolaitis","year":"1987","journal-title":"Proc. 19th ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(93)90218-I_BIB73","first-page":"2","article-title":"0\u20131 laws and decision problems for fragments of second-order logic","author":"Kolaitis","year":"1988","journal-title":"Proc. 3rd IEEE Symp. on Logic in Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB74","series-title":"Research Report RJ 7508","article-title":"0\u20131 laws for fragments of second-order logic","author":"Kolaitis","year":"1990"},{"key":"10.1016\/0304-3975(93)90218-I_BIB75","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1109\/LICS.1990.113742","article-title":"0\u20131 laws for infinitary logics","author":"Kolaitis","year":"1990","journal-title":"Proc. 5th IEEE Symp. on Logic in Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB76_1","first-page":"115","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"10.1016\/0304-3975(93)90218-I_BIB76_2","first-page":"265","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problems Inform. Transmission"},{"key":"10.1016\/0304-3975(93)90218-I_BIB77","series-title":"Unsolvable Classes of Quantificational Formulas","author":"Lewis","year":"1979"},{"key":"10.1016\/0304-3975(93)90218-I_BIB78","first-page":"17","article-title":"The relational model for systems of automatic testing","volume":"4","author":"Livchak","year":"1982","journal-title":"Automatic Documentation and Mathematical Linguistics"},{"key":"10.1016\/0304-3975(93)90218-I_BIB79","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0003-4843(80)90014-5","article-title":"Almost sure theories","author":"Lynch","year":"1980","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB80","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1090\/S0002-9947-1985-0768725-2","article-title":"Probabilities of first-order sentences about unary functions","volume":"287","author":"Lynch","year":"1985","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0304-3975(93)90218-I_BIB81","series-title":"The Theory of Relational Databases","author":"Maier","year":"1983"},{"key":"10.1016\/0304-3975(93)90218-I_BIB82","series-title":"Model-Theoretic Logics","first-page":"645","article-title":"Compactness, embeddings and definability","author":"Makowsky","year":"1985"},{"key":"10.1016\/0304-3975(93)90218-I_BIB83","first-page":"280","article-title":"The 0\u20131 law fails for the class of existential second-order G\u00f6del sentences with equality","author":"Pacholski","year":"1989","journal-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(93)90218-I_BIB84","doi-asserted-by":"crossref","first-page":"331","DOI":"10.4064\/aa-9-4-331-340","article-title":"Universal graphs and universal functions","volume":"9","author":"Rado","year":"1964","journal-title":"Acta Arith."},{"key":"10.1016\/0304-3975(93)90218-I_BIB85","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(93)90218-I_BIB86","first-page":"160","article-title":"Problem #1: Ein ungel\u00f3stes problem in der symbolischen logik","volume":"17","author":"Scholz","year":"1952","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB87","series-title":"Classification Theory and the Number of Non-Isomorphic Models","author":"Shelah","year":"1978"},{"key":"10.1016\/0304-3975(93)90218-I_BIB88","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/S0894-0347-1988-0924703-8","article-title":"Zero-one laws for sparse random graphs","volume":"1","author":"Shelah","year":"1988","journal-title":"J. Amer. Math. Soc."},{"key":"10.1016\/0304-3975(93)90218-I_BIB89","series-title":"Mathematical Logic","author":"Shoenfield","year":"1967"},{"key":"10.1016\/0304-3975(93)90218-I_BIB90","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","article-title":"The method of forced enumeration for nondeterministic automata","volume":"26","author":"Szelepcs\u00e9nyi","year":"1988","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(93)90218-I_BIB91","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2307\/2964569","article-title":"A counterexample to a conjecture of Scott and Suppes","volume":"24","author":"Tait","year":"1959","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB92_1","first-page":"56","article-title":"The asymptotic truth value of infinite formulas","author":"Talanov","year":"1984","journal-title":"Proc. All-Union Seminar on Discrete Mathematics and its Applications"},{"key":"10.1016\/0304-3975(93)90218-I_BIB92_2","first-page":"03054","article-title":"The asymptotic truth value of infinite formulas","volume":"89g","author":"Talanov","year":"1989","journal-title":"Math. Rev."},{"key":"10.1016\/0304-3975(93)90218-I_BIB93","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1016\/S1385-7258(54)50074-0","article-title":"Contributions to the theory of models I, II","volume":"16","author":"Tarski","year":"1954","journal-title":"Indag. Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB94","first-page":"569","article-title":"Impossibility of an algorithm for the decision problem in finite classes","volume":"70","author":"Trakhtenbrot","year":"1950","journal-title":"Dok. Akad. Nauk SSSR"},{"key":"10.1016\/0304-3975(93)90218-I_BIB95","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(84)90166-3","article-title":"On the definability of properties of finite graphs","volume":"49","author":"Tur\u00e1n","year":"1984","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(93)90218-I_BIB96","series-title":"Database and Knowledge-Base Systems, Vols. I and II","author":"Ullman","year":"1989"},{"key":"10.1016\/0304-3975(93)90218-I_BIB97","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","article-title":"Relative complexity of checking and evaluating","volume":"5","author":"Valiant","year":"1976","journal-title":"Inform. Process."},{"key":"10.1016\/0304-3975(93)90218-I_BIB98","first-page":"137","article-title":"The complexity of relational query languages","author":"Vardi","year":"1982","journal-title":"Proc. 14th ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(93)90218-I_BIB99","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1109\/SFCS.1982.75","article-title":"On decomposition of relational databases","author":"Vardi","year":"1982","journal-title":"Proc. 23rd IEEE Symp. on Foundations of Computer Science"},{"issue":"1","key":"10.1016\/0304-3975(93)90218-I_BIB100","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2307\/2964336","article-title":"Sentences true in all constructive models","volume":"25","author":"Vaught","year":"1960","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(93)90218-I_BIB101","article-title":"Relativization, reducibilities, and the exponential hierarchy","author":"Wilson","year":"1980","journal-title":"Master's Thesis"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759390218I?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759390218I?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,14]],"date-time":"2021-05-14T22:42:29Z","timestamp":1621032149000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759390218I"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,8]]},"references-count":104,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,8]]}},"alternative-id":["030439759390218I"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(93)90218-i","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1993,8]]}}}