{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:00:14Z","timestamp":1787508014734,"version":"build-2736575974"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6585,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1996,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Motivated by problems that arise in computing\n                    <jats:italic>degrees of belief<\/jats:italic>\n                    , we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences\n                    <jats:italic>\u03c6<\/jats:italic>\n                    and\n                    <jats:italic>\u03b8<\/jats:italic>\n                    , we consider the structures with domain {1, \u2026,\n                    <jats:italic>N<\/jats:italic>\n                    } that satisfy\n                    <jats:italic>\u03b8<\/jats:italic>\n                    , and compute the fraction of them in which\n                    <jats:italic>\u03c6<\/jats:italic>\n                    is true. We then consider what happens to this fraction as\n                    <jats:italic>N<\/jats:italic>\n                    gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic\n                    <jats:italic>conditional<\/jats:italic>\n                    probabilities. As shown by Liogon'ki\u012d [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'ki\u012d also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.\n                  <\/jats:p>","DOI":"10.2307\/2275609","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:57:36Z","timestamp":1146941856000},"page":"250-276","source":"Crossref","is-referenced-by-count":11,"title":["Asymptotic conditional probabilities: The non-unary case"],"prefix":"10.1017","volume":"61","author":[{"given":"Adam J.","family":"Grove","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph Y.","family":"Halpern","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daphne","family":"Koller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200017758_ref030","volume-title":"Die principien der wahrscheinlichkeitsrechnung und rational expectation","author":"von Kries","year":"1886"},{"key":"S0022481200017758_ref028","volume-title":"Summability theory and applications","author":"Powell","year":"1972"},{"key":"S0022481200017758_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(80)90014-5"},{"key":"S0022481200017758_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90065-P"},{"key":"S0022481200017758_ref021","volume-title":"A treatise on probability","author":"Keynes","year":"1921"},{"key":"S0022481200017758_ref020","first-page":"15","volume-title":"The maximum entropy formalism","author":"Jaynes","year":"1978"},{"key":"S0022481200017758_ref018","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1613\/jair.61","article-title":"Random worlds and maximum entropy","volume":"2","author":"Grove","year":"1994","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S0022481200017758_ref017","first-page":"294","volume-title":"Proc. 24th ACM symp. on theory of computing","author":"Grove","year":"1992"},{"key":"S0022481200017758_ref015","doi-asserted-by":"crossref","DOI":"10.1063\/1.4822863","volume-title":"Concrete mathematics\u2014a foundation for computer science","author":"Graham","year":"1989"},{"key":"S0022481200017758_ref012","first-page":"77","volume-title":"International congress of logic methodology and philosophy of science","author":"Gaifman","year":"1960"},{"key":"S0022481200017758_ref010","first-page":"50","volume":"41","author":"Fagin","year":"1976","journal-title":"Probabilities on finite models"},{"key":"S0022481200017758_ref009","volume-title":"The decision problem: Solvable classes of quantificational formulas","author":"Dreben","year":"1979"},{"key":"S0022481200017758_ref008","volume-title":"Entropy in relation to incomplete knowledge","author":"Denbigh","year":"1985"},{"key":"S0022481200017758_ref007","volume-title":"Essai philosophique sur les probabilit\u00e9s","author":"de Laplace","year":"1951"},{"key":"S0022481200017758_ref002","volume-title":"Statistical foundations for default reasoning","author":"Bacchus","year":"1993"},{"key":"S0022481200017758_ref001","first-page":"602","volume-title":"Proceedings of the national conference on artificial intelligence (AAAI '92)","author":"Bacchus","year":"1992"},{"key":"S0022481200017758_ref014","first-page":"17","article-title":"Range and degree of realizability of formulas in the restricted predicate calculus","volume":"2","author":"Glebski\u012d","year":"1969","journal-title":"Kibernetika"},{"key":"S0022481200017758_ref029","first-page":"569","article-title":"Impossibility of an algorithm for the decision problem in finite classes","volume":"70","author":"Trakhtenbrot","year":"1950","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200017758_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0931-7"},{"key":"S0022481200017758_ref016","article-title":"Asymptotic conditional probabilities for first-order logic, Part II: the unary case","author":"Grove","year":"1993","journal-title":"SIAM Journal on Computing"},{"key":"S0022481200017758_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0888-613X(89)90012-1"},{"key":"S0022481200017758_ref006","first-page":"353","volume-title":"Proceedings of the 1987 NATO advanced study institute on algorithms and order","author":"Compton","year":"1988"},{"key":"S0022481200017758_ref005","first-page":"198","volume-title":"Proceedings of the eighth international joint conference on artificial intelligence (IJCAI '83)","author":"Cheeseman","year":"1983"},{"key":"S0022481200017758_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90116-9"},{"key":"S0022481200017758_ref004","volume-title":"The continuum of inductive methods","author":"Carnap","year":"1952"},{"key":"S0022481200017758_ref023","volume-title":"Unsolvable classes of quantificational formulas","author":"Lewis","year":"1979"},{"key":"S0022481200017758_ref003","volume-title":"Logical foundations of probability","author":"Carnap","year":"1950"},{"key":"S0022481200017758_ref019","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200017758_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BF01146404"},{"key":"S0022481200017758_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759729"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200017758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T15:07:14Z","timestamp":1557760034000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200017758\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,3]]}},"alternative-id":["S0022481200017758"],"URL":"https:\/\/doi.org\/10.2307\/2275609","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}