{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:08Z","timestamp":1740109268011,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T00:00:00Z","timestamp":1452556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/K016075\/1"],"award-info":[{"award-number":["EP\/K016075\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00453-016-0113-3","type":"journal-article","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T13:57:10Z","timestamp":1452607030000},"page":"1106-1138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Generalised and Quotient Models for Random And\/Or\u00a0Trees and Application to Satisfiability"],"prefix":"10.1007","volume":"76","author":[{"given":"Antoine","family":"Genitrini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e9cile","family":"Mailler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,12]]},"reference":[{"issue":"3","key":"113_CR1","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","volume":"36","author":"D Achlioptas","year":"2006","unstructured":"Achlioptas, D., Moore, C.: Random k-SAT: two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740\u2013762 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4\u20135","key":"113_CR2","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1017\/S0963548304006273","volume":"13","author":"B Chauvin","year":"2004","unstructured":"Chauvin, B., Flajolet, P., Gardy, D., Gittenberger, B.: And\/Or trees revisited. Comb. Probab. Comput. 13(4\u20135), 475\u2013497 (2004)","journal-title":"Comb. Probab. Comput."},{"key":"113_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20567","author":"B Chauvin","year":"2014","unstructured":"Chauvin, B., Gardy, D., Mailler, C.: A sprouting tree model for random boolean functions. Random Struct. Algorithms (2014). doi: 10.1002\/rsa.20567","journal-title":"Random Struct. Algorithms"},{"key":"113_CR4","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: The asymptotic k-SAT threshold. In: 46th Symposium on Theory of Computing, STOC, pp. 804\u2013813 (2014)","DOI":"10.1145\/2591796.2591822"},{"key":"113_CR5","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Panagiotou, K.: Going after the k-SAT threshold. In: 45th Symposium on Theory of Computing, STOC, pp. 705\u2013714 (2013)","DOI":"10.1145\/2488608.2488698"},{"issue":"1","key":"113_CR6","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/s00453-009-9308-1","volume":"59","author":"H Daud\u00e9","year":"2011","unstructured":"Daud\u00e9, H., Ravelomanana, V.: Random 2-XORSAT phase transition. Algorithmica 59(1), 48\u201365 (2011)","journal-title":"Algorithmica"},{"key":"113_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"key":"113_CR8","doi-asserted-by":"crossref","unstructured":"Fournier, H., Gardy, D., Genitrini, A.: Balanced And\/Or trees and linear threshold functions. In: 6th SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 51\u201357. New York, USA (2009)","DOI":"10.1137\/1.9781611972993.8"},{"issue":"3","key":"113_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1002\/rsa.20379","volume":"40","author":"H Fournier","year":"2012","unstructured":"Fournier, H., Gardy, D., Genitrini, A., Gittenberger, B.: The fraction of large random trees representing a given boolean function in implicational logic. Random Struct. Algorithms 40(3), 317\u2013349 (2012). doi: 10.1002\/rsa.20379","journal-title":"Random Struct. Algorithms"},{"key":"113_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2014.12.025","volume":"570","author":"A Genitrini","year":"2015","unstructured":"Genitrini, A., Gittenberger, B., Kraus, V., Mailler, C.: Associative and commutative tree representations for boolean functions. Theor. Comput. Sci. 570, 70\u2013101 (2015). doi: 10.1016\/j.tcs.2014.12.025","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"113_CR11","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1016\/j.apal.2011.09.011","volume":"163","author":"A Genitrini","year":"2012","unstructured":"Genitrini, A., Kozik, J.: In the full propositional logic, 5\/8 of classical tautologies are intuitionistically valid. Ann. Pure Appl. Logic 163(7), 875\u2013887 (2012). doi: 10.1016\/j.apal.2011.09.011","journal-title":"Ann. Pure Appl. Logic"},{"key":"113_CR12","doi-asserted-by":"publisher","unstructured":"Genitrini, A., Kozik, J., Zaionc, M.: Intuitionistic vs. classical tautologies, quantitative comparison. In: TYPES, pp. 100\u2013109 (2007). doi: 10.1007\/978-3-540-68103-8_7","DOI":"10.1007\/978-3-540-68103-8_7"},{"key":"113_CR13","doi-asserted-by":"crossref","unstructured":"Genitrini, A., Mailler, C.: Equivalence classes of random boolean trees and application to the catalan satisfiability problem. In: Springer-Verlag (ed.) Latin American Theoretical INformatics, pp. 466\u2013477. Motevideo, Uruguay (2014)","DOI":"10.1007\/978-3-642-54423-1_41"},{"key":"113_CR14","doi-asserted-by":"crossref","unstructured":"Kozik, J.: Subcritical pattern languages for And\/Or trees. In: Fifth Colloquium on Mathematics and Computer Science. DMTCS Proceedings (2008)","DOI":"10.46298\/dmtcs.3582"},{"key":"113_CR15","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<337::AID-RSA4>3.0.CO;2-X","volume":"10","author":"H Lefmann","year":"1997","unstructured":"Lefmann, H., Savick\u00fd, P.: Some typical properties of large And\/Or Boolean formulas. Random Struct. Algorithms 10, 337\u2013351 (1997)","journal-title":"Random Struct. Algorithms"},{"key":"113_CR16","first-page":"120","volume":"1","author":"OB Lupanov","year":"1958","unstructured":"Lupanov, O.B.: A method of circuit synthesis. Izvesitya VUZ Radiofiz 1, 120\u2013140 (1958). (in Russian)","journal-title":"Izvesitya VUZ Radiofiz"},{"issue":"2","key":"113_CR17","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"JH Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"113_CR18","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0168-0072(94)90011-6","volume":"70","author":"JB Paris","year":"1994","unstructured":"Paris, J.B., Vencovsk\u00e1, A., Wilmers, G.M.: A natural prior probability distribution derived from the propositional calculus. Ann. Pure Appl. Logic 70, 243\u2013285 (1994)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"4","key":"113_CR19","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF00049427","volume":"40","author":"M Sibuya","year":"1988","unstructured":"Sibuya, M.: Log-concavity of Stirling numbers and unimodality of Stirling distributions. Ann. Inst. Stat. Math. 40(4), 693\u2013714 (1988)","journal-title":"Ann. Inst. Stat. Math."},{"key":"113_CR20","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/(SICI)1098-2418(199707)10:4<453::AID-RSA3>3.0.CO;2-T","volume":"10","author":"AR Woods","year":"1997","unstructured":"Woods, A.R.: Coloring rules for finite trees, and probabilities of monadic second order sequences. Random Struct. Algorithms 10, 453\u2013485 (1997)","journal-title":"Random Struct. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0113-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0113-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0113-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0113-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T12:44:11Z","timestamp":1654087451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0113-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,12]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["113"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0113-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,1,12]]}}}