{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T02:08:02Z","timestamp":1650506882511},"reference-count":45,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6036,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1997,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let<jats:italic>\u03c6<\/jats:italic>be a monadic second order sentence about a finite structure from a class<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200016108_inline1\" \/>which is closed under disjoint unions and has components. Compton has conjectured that if the number of<jats:italic>n<\/jats:italic>element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities<jats:italic>\u03bd(\u03c6)<\/jats:italic>(<jats:italic>\u03bc(\u03c6)<\/jats:italic>respectively) for<jats:italic>\u03c6<\/jats:italic>always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200016108_inline1\" \/>-structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.<\/jats:p>","DOI":"10.2307\/2275580","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T23:01:58Z","timestamp":1146956518000},"page":"925-949","source":"Crossref","is-referenced-by-count":4,"title":["Counting finite models"],"prefix":"10.1017","volume":"62","author":[{"given":"Alan R.","family":"Woods","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200016108_ref045","volume-title":"Research Report 15","author":"Woods","year":"1995"},{"key":"S0022481200016108_ref044","volume-title":"generatingfunctionology","author":"Wilf","year":"1990"},{"key":"S0022481200016108_ref043","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060205"},{"key":"S0022481200016108_ref040","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BFb0023784","volume-title":"Computer science logic. proc. 5th workshop, CSL'91 Berne Switzerland, October 1991","volume":"626","author":"Tyszkiewicz","year":"1992"},{"key":"S0022481200016108_ref038","first-page":"341","volume-title":"Order","volume":"7","author":"Spencer","year":"1990"},{"key":"S0022481200016108_ref036","first-page":"385","article-title":"On connected graphs, I","volume":"4","author":"R\u00e9nyi","year":"1959","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"S0022481200016108_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342974"},{"key":"S0022481200016108_ref034","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4664-0"},{"key":"S0022481200016108_ref033","doi-asserted-by":"publisher","DOI":"10.1007\/BF02546665"},{"key":"S0022481200016108_ref032","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"S0022481200016108_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579158"},{"key":"S0022481200016108_ref028","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050115"},{"key":"S0022481200016108_ref037","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"S0022481200016108_ref027","first-page":"145","article-title":"Convergence laws for random words","volume":"7","author":"Lynch","year":"1993","journal-title":"Australian Journal of Combinatorics"},{"key":"S0022481200016108_ref024","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728496"},{"key":"S0022481200016108_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342903"},{"key":"S0022481200016108_ref021","first-page":"479","volume-title":"Model-theoretic logics","author":"Gurevich","year":"1985"},{"key":"S0022481200016108_ref020","volume-title":"Combinatorial enumeration","author":"Goulden","year":"1983"},{"key":"S0022481200016108_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190254"},{"key":"S0022481200016108_ref016","unstructured":"Foy J. M. , Probability and enumeration results in the theory of finite models, Ph.D. thesis , Yale University, New Haven CT, 1994."},{"key":"S0022481200016108_ref015","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-1-4612-3466-1_10","volume-title":"Feasible mathematics. A Mathematical Sciences Institute Workshop, Ithaca, New York, June 1989","author":"Foy","year":"1990"},{"key":"S0022481200016108_ref013","volume-title":"Collected papers of R. A. Fisher","author":"Fisher","year":"1974"},{"key":"S0022481200016108_ref012","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-1809.1941.tb02302.x"},{"key":"S0022481200016108_ref011","volume-title":"Introduction to probability theory and its applications","volume":"2","author":"Feller","year":"1971"},{"key":"S0022481200016108_ref010","first-page":"50","volume":"41","author":"Fagin","year":"1976","journal-title":"Probabilities on finite models"},{"key":"S0022481200016108_ref009","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"S0022481200016108_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90019-3"},{"key":"S0022481200016108_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF02007559"},{"key":"S0022481200016108_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80027-9"},{"key":"S0022481200016108_ref001","doi-asserted-by":"publisher","DOI":"10.1137\/1016082"},{"key":"S0022481200016108_ref023","volume-title":"Graphical enumeration","author":"Harary","year":"1973"},{"key":"S0022481200016108_ref026","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0768725-2"},{"key":"S0022481200016108_ref042","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050120"},{"key":"S0022481200016108_ref014","first-page":"238","article-title":"Asymptotic number of nonisomorphic finite models with function symbols (preliminary report)","volume":"843","author":"Foy","year":"1988","journal-title":"Abstracts of the American Mathematical Society"},{"key":"S0022481200016108_ref017","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","volume":"1","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Pub. Sri. Univ. Alger. Ser. A."},{"key":"S0022481200016108_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90119-1"},{"key":"S0022481200016108_ref030","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840501"},{"key":"S0022481200016108_ref008","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S0022481200016108_ref039","first-page":"56","volume-title":"Proceedings of the all-Union seminar on discrete mathematics and its applications (Moscow 1984)","author":"Talanov","year":"1986"},{"key":"S0022481200016108_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90017-0"},{"key":"S0022481200016108_ref019","first-page":"17","article-title":"Range and degree of readability of formulas in the restricted predicate calculus","volume":"5","author":"Glebski\u01d0","year":"1969","journal-title":"Kibernetika (Kiev)"},{"key":"S0022481200016108_ref031","volume-title":"Counting labelled trees","volume":"1","author":"Moon","year":"1970"},{"key":"S0022481200016108_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90112-8"},{"key":"S0022481200016108_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90009-5"},{"key":"S0022481200016108_ref041","first-page":"425","volume-title":"Computer science logic. proc. 6th workshop, CSL'92 San Miniato, 1992","volume":"702","author":"Tyszkiewicz","year":"1993"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200016108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T14:23:32Z","timestamp":1586874212000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200016108\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,9]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,9]]}},"alternative-id":["S0022481200016108"],"URL":"https:\/\/doi.org\/10.2307\/2275580","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,9]]}}}