{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T06:54:55Z","timestamp":1760079295708},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_6","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"84-98","source":"Crossref","is-referenced-by-count":8,"title":["0\u20131 Laws for Fragments of Existential Second-Order Logic: A Survey"],"prefix":"10.1007","author":[{"given":"Phokion G.","family":"Kolaitis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"6_CR1","unstructured":"Abiteboul, S, Hull, R., Vianu, V.: Foundations of Databases. Addision-Wesley, 1995."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"572","DOI":"10.2307\/2273534","volume":"43","author":"F. D. Abramson","year":"1978","unstructured":"Abramson, F. D., Harrington, L.A.: Models without indiscernibles. J. Symbolic Logic 431978,pp. 572\u2013600.","journal-title":"J. Symbolic Logic"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer-Verlag, 1997.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"6_CR4","unstructured":"Bollobas, B: Random Graphs. Academic Press, 1985"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observation. Ann. Math. Stat 23(1952), pp. 493\u2013509.","journal-title":"Ann. Math. Stat"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. J. ACM 28(1981), pp. 114\u2013133.","journal-title":"J. ACM"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Compton, K.J.: 0-1 laws in logic and combinatorics, in NATO Adv. Study Inst. on Algorithms and Order I. Rival, ed., D. Reidel, 1988, pp. 353\u2013383.","DOI":"10.1007\/978-94-009-2639-4_10"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0012-365X(90)90327-E","volume":"82","author":"W. F. Vega de la","year":"1990","unstructured":"de la Vega, W.F.: Kernel on random graphs. Discrete Mathematics 821990), pp. 213\u2013217.","journal-title":"Discrete Mathematics"},{"key":"6_CR9","unstructured":"Dreben, D., and Goldfarb, W.D.: The Decision Problem: Solvable Classes of Quantificational Formulas. Addison-Wesley, 1979."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Ebbinghaus, H. D., Flum, J.: Finite Model Theorey, Springer-Verlag, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"6_CR11","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial time recognizable sets. Complexity of Computations R. Karp, ed., SIAM-AMS Proc. 7(1974), pp. 43\u201373."},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","unstructured":"Fagin, R.: Probabilities on finite models. J. Symbolic Logic 411976, pp. 50\u201358.","journal-title":"J. Symbolic Logic"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02759729","volume":"2","author":"H. Gaifman","year":"1964","unstructured":"Gaifman, H.: Concerning measures in first-order calculi. Israel J. Math. 2(1964). pp. 1\u201318.","journal-title":"Israel J. Math"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/BF01071084","volume":"5","author":"Y.V. Glebskii","year":"1969","unstructured":"Glebskii, Y.V., Kogan, D.I., Liogonkii. M.I., Talanov, V.A.: Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics 5(1969), pp. 142\u2013154.","journal-title":"Cybernetics"},{"key":"6_CR15","first-page":"27","volume":"2","author":"K. G\u00f6del","year":"1932","unstructured":"G\u00f6del, K.: Ein Spezialfall des Entscheidungsproblems der theoretischen Logik, Ergebn. math. Kolloq. 2(1932), pp. 27\u201328.","journal-title":"Ergebn. math. Kolloq"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1090\/S0273-0979-1984-15207-8","volume":"10","author":"W.D. Goldfarb","year":"1984","unstructured":"Goldfarb, W.D.: The G\u00f6del class with equality is unsolvable. Bull. Amer. Math. Soc. (New Series) 101984, pp. 113\u2013115.","journal-title":"Bull. Amer. Math. Soc. (New Series)"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/S0019-9958(83)80043-6","volume":"52","author":"E. Grandjean","year":"1983","unstructured":"Grandjean, E.: Complexity of the first-order theory of almost all structures. Information and Control 521983, pp. 180\u2013204.","journal-title":"Information and Control"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/421196","volume":"3","author":"E. Gr\u00e4del","year":"1997","unstructured":"Gr\u00e4del, E., Kolaitis P.G., Vardi M.Y.: On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3(1997), 53\u201369.","journal-title":"Bulletin of Symbolic Logic"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.2307\/2273674","volume":"48","author":"Y. Gurevich","year":"1983","unstructured":"Gurevich, Y., and Shelah, S.: Random models and the G\u00f6del case of the decision problem. J. of Symbolic Logic 48(1983), pp. 1120\u20131124.","journal-title":"J. of Symbolic Logic"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis, J., Immerman, N., Sewelson, J.: Sparse sets in NP-P-EXPTIME vs. NEXPTIME. Information and Control 65(1985), pp. 159\u2013181.","journal-title":"Information and Control"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Desctiptive Complexity. Springger-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"6_CR22","unstructured":"Kaufmann, M.: A counterexample to the 0-1 law for existential monadic second-order logic. CLI Internal Note 32, Computational Logic Inc., Dec. 1987."},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(85)90112-8","volume":"54","author":"M. Kauffman","year":"1985","unstructured":"Kauffman, M., Shelah, S: On random models of finite power and monadic logic. Discrete Mathematics 54(1985), pp. 285\u2013293.","journal-title":"Discrete Mathematics"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., Vardi, M.Y: The decision problem for the probabilities of higherorder properties. Proc. 19th ACM Symp. on Theory of Computing, New York, May 1987, pp. 425\u2013435.","DOI":"10.1145\/28395.28441"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y: 0-1 laws for fragments of second-order logic-an overview. Logic from Computer Science Proc. of Workshop, 1989), 1992, pp. 265\u2013286.","DOI":"10.1007\/978-1-4612-2822-6_10"},{"key":"6_CR26","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0890-5401(90)90065-P","volume":"87","author":"P. Kolaitis","year":"1990","unstructured":"Kolaitis, P., Vardi, M.Y: 0-1 laws and decision problems for fragments of second-order logic. Information and Computation 87(1990), pp. 302\u2013338.","journal-title":"Information and Computation"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(96)00035-X","volume":"58","author":"Lacoste","year":"1996","unstructured":"Lacoste: Finitistic proofs of 0-1 laws for fragments of second-order logic. Information Processing Letters 58(1996), pp. 1\u20134.","journal-title":"Information Processing Letters"},{"key":"6_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(97)00086-8","volume":"184","author":"Lacoste","year":"1997","unstructured":"Lacoste, T.: 0-1 Laws by preservation. Theoretical Computer Science 184(1997), pp. 237\u2013245.","journal-title":"Theoretical Computer Science"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Le Bars, J.M.: Fragments of existential second-order logic without 0-1 laws. Proc. 13th IEEE Symp. on Logic in Computer Science, 1998, pp. 525\u2013536.","DOI":"10.1109\/LICS.1998.705685"},{"key":"6_CR30","doi-asserted-by":"publisher","first-page":"67","DOI":"10.2307\/421076","volume":"6","author":"J.M. LeBars","year":"2000","unstructured":"LeBars, J.M.: Counterexamples of the 0-1 law for fragments of existential second-order logic: an overview. Bulletin of Symbolic Logic 6(2000), pp. 67\u201382.","journal-title":"Bulletin of Symbolic Logic"},{"key":"6_CR31","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/malq.19750210118","volume":"21","author":"M. Mortimer","year":"1975","unstructured":"Mortimer, M.: On language with two variables, Zeit, f\u00fcr Math. Logik und Grund, der Math. 21(1975), pp. 135\u2013140.","journal-title":"Zeit, f\u00fcr Math. Logik und Grund"},{"key":"6_CR32","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0097-3165(77)90004-8","volume":"22","author":"J. Ne\u0161et\u0159il","year":"1977","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: Partitions of finite relational and set systems. J. Combinatorial Theory A 22(1977), pp. 289\u2013312.","journal-title":"J. Combinatorial Theory A"},{"key":"6_CR33","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0097-3165(83)90055-9","volume":"34","author":"J. Ne\u0161et\u0159il","year":"1983","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: Ramsey classes of set systems. J. Combinatorial Theory A 34 (1983), pp. 183\u2013201.","journal-title":"J. Combinatorial Theory A"},{"key":"6_CR34","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. P\u00f3sa","year":"1976","unstructured":"P\u00f3sa, L.: Hamiltonian circuits in random graphs. Discrete Math. 14(1976), pp. 359\u2013364.","journal-title":"Discrete Math"},{"key":"6_CR35","doi-asserted-by":"publisher","first-page":"427","DOI":"10.2307\/2274691","volume":"56","author":"L. Pacholski","year":"1991","unstructured":"Pacholski, L., Szwast, L.: Asymptotic probabilities of existential second-order G\u00f6del sentences. Journal of Symbolic Logic 56(1991), pp. 427\u2013438.","journal-title":"Journal of Symbolic Logic"},{"key":"6_CR36","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/inco.1993.1062","volume":"107","author":"L. Pacholski","year":"1993","unstructured":"Pacholski, L., Szwast, W.: A counterexample to the 0-1 law for the class of existential second-order minimal G\u00f6del sentences with equality. Information and Computation 107(1993), pp. 91\u2013103.","journal-title":"Information and Computation"},{"key":"6_CR37","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"30","author":"F.P. Ramsey","year":"1928","unstructured":"Ramsey, F.P.: On a problem in formal logic. Proc. London Math. Soc. 30(1928). pp. 264\u2013286.","journal-title":"Proc. London Math. Soc"},{"key":"6_CR38","first-page":"569","volume":"70","author":"B.A. Trakhtenbrot","year":"1950","unstructured":"Trakhtenbrot, B.A.: The impossibilty of an algorithm for the decision problem for finite models. Doklady Akademii Nauk SSR 70(1950), PP. 569\u2013572.","journal-title":"Doklady Akademii Nauk SSR"},{"key":"6_CR39","doi-asserted-by":"crossref","first-page":"277","DOI":"10.3233\/FI-1994-2041","volume":"20","author":"L. Tendera","year":"1994","unstructured":"Tendera, L.: A note on asymptotic probabilities of existential second-order minimal classes: the last step. Fundamenta Informaticae 20(1994), pp. 277\u2013285.","journal-title":"Fundamenta Informaticae"},{"key":"6_CR40","doi-asserted-by":"publisher","first-page":"304","DOI":"10.2307\/2275743","volume":"62","author":"A. Vedo","year":"1997","unstructured":"Vedo, A.: Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences. J. Symbolic Logic 62(1997), pp. 304\u2013319.","journal-title":"J. Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T19:14:55Z","timestamp":1587496495000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}