{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T15:47:40Z","timestamp":1774367260178,"version":"3.50.1"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T00:00:00Z","timestamp":1095984000000},"content-version":"unspecified","delay-in-days":85,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>We consider Boolean functions over <jats:inline-formula>$n$<\/jats:inline-formula> variables. Any such function can be represented (and computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes, and many different trees can represent the same function, so that a fundamental question is related to the so-called <jats:italic>complexity<\/jats:italic> of a Boolean function: <jats:inline-formula>$L(f):=$<\/jats:inline-formula> minimal size of a tree computing <jats:inline-formula>$f$<\/jats:inline-formula>.<\/jats:p>\n\t  <jats:p>The existence of a limiting probability distribution <jats:inline-formula>$P(\\cdot)$<\/jats:inline-formula> on the set of and\/or trees was shown by Lefmann and Savick\u00fd [8]. We give here an alternative proof, which leads to effective computation in simple cases. We also consider the relationship between the probability <jats:inline-formula>$P(f)$<\/jats:inline-formula> and the complexity <jats:inline-formula>$L(f)$<\/jats:inline-formula> of a Boolean function <jats:inline-formula>$f$<\/jats:inline-formula>. A detailed analysis of the functions enumerating some sub-families of trees, and of their radius of convergence, allows us to improve on the upper bound of <jats:inline-formula>$P(f)$<\/jats:inline-formula>, established by Lefmann and Savick\u00fd.<\/jats:p>","DOI":"10.1017\/s0963548304006273","type":"journal-article","created":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T13:28:19Z","timestamp":1096032499000},"page":"475-497","source":"Crossref","is-referenced-by-count":28,"title":["And\/Or Trees Revisited"],"prefix":"10.1017","volume":"13","author":[{"given":"B.","family":"CHAUVIN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"FLAJOLET","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"GARDY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"GITTENBERGER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2004,9,24]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T15:46:58Z","timestamp":1750434418000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006273\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":0,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0963548304006273"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006273","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]}}}