{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:19:48Z","timestamp":1725517188643},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540852377"},{"type":"electronic","value":"9783540852384"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85238-4_28","type":"book-chapter","created":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T15:34:36Z","timestamp":1219073676000},"page":"347-362","source":"Crossref","is-referenced-by-count":0,"title":["Complexity and Limiting Ratio of Boolean Functions over Implication"],"prefix":"10.1007","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00e8le","family":"Gardy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Genitrini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Gittenberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Zaionc, M.: Statistics of implicational logic. Electronic Notes in Theoretical Computer Science\u00a084 (2003)","DOI":"10.1016\/S1571-0661(04)80856-9"},{"issue":"3","key":"28_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:STUD.0000032101.88511.93","volume":"76","author":"Z. Kostrzycka","year":"2004","unstructured":"Kostrzycka, Z., Zaionc, M.: Statistics of intuitionnistic versus classical logic. Studia Logica\u00a076(3), 307\u2013328 (2004)","journal-title":"Studia Logica"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Gardy, D.: Random boolean expressions. In: Colloquium on Computational Logic and Applications (2006)","DOI":"10.46298\/dmtcs.3475"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Fournier, H., Gardy, D., Genitrini, A., Zaionc, M.: Classical and intuitionistic logic are asymptotically identical. In: CSL, pp. 177\u2013193 (2007)","DOI":"10.1007\/978-3-540-74915-8_16"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0168-0072(94)90011-6","volume":"70","author":"J.B. Paris","year":"1994","unstructured":"Paris, J.B., Vencovsk\u00e1, A., Wilmers, G.M.: A natural prior probability distribution derived from the propositional calculus. Annals of Pure and Applied Logic\u00a070, 243\u2013285 (1994)","journal-title":"Annals of Pure and Applied Logic"},{"key":"28_CR6","doi-asserted-by":"publisher","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 Structures and Algorithms\u00a010, 337\u2013351 (1997)","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"28_CR7","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1002\/(SICI)1098-2418(199707)10:4<453::AID-RSA3>3.0.CO;2-T","volume":"10","author":"A.R. Woods","year":"1997","unstructured":"Woods, A.R.: Coloring rules for finite trees, and probabilities of monadic second order sentences. Random Struct. Algorithms\u00a010(4), 453\u2013485 (1997)","journal-title":"Random Struct. Algorithms"},{"issue":"4-5","key":"28_CR8","doi-asserted-by":"publisher","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. Combinatorics, Probability and Computing\u00a013(4-5), 475\u2013497 (2004)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"5","key":"28_CR9","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1017\/S0960129599002959","volume":"10","author":"M. Moczurad","year":"2000","unstructured":"Moczurad, M., Tyszkiewicz, J., Zaionc, M.: Statistical properties of simple types. Mathematical Structures in Computer Science\u00a010(5), 575\u2013594 (2000)","journal-title":"Mathematical Structures in Computer Science"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Kostrzycka, Z.: On the density of truth of implicational parts of intuitionistic and classical logics. J. of Applied Non-Classical Logics\u00a013(2) (2003)","DOI":"10.3166\/jancl.13.391-421"},{"key":"28_CR11","first-page":"67","volume":"39","author":"M. Zaionc","year":"2005","unstructured":"Zaionc, M.: On the asymptotic density of tautologies in logic of implication and negation. Reports on Mathematical Logic\u00a039, 67\u201387 (2005)","journal-title":"Reports on Mathematical Logic"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Kostrzycka, Z.: On the density of truth in modal logics. In: Mathematics and Computer Science, Nancy (France); Proceedings in DMTCS (September 2006) (to appear)","DOI":"10.46298\/dmtcs.3500"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.entcs.2005.06.022","volume":"140","author":"G. Matecki","year":"2005","unstructured":"Matecki, G.: Asymptotic density for equivalence. Electronic Notes in Theoretical Computer Science\u00a0140, 81\u201391 (2005)","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1017\/S0960129507006391","volume":"18","author":"Z. Kostrzycka","year":"2008","unstructured":"Kostrzycka, Z.: On asymptotic divergency in equivalential logics. Mathematical Structures in Computer Science\u00a018, 311\u2013324 (2008)","journal-title":"Mathematical Structures in Computer Science"},{"key":"28_CR15","unstructured":"Woods, A.: On the probability of absolute truth for and\/or formulas. Bulletin of Symbolic Logic\u00a012(3) (2005)"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Kozic, J.: Subcritical pattern languages for and\/or trees. Technical report (2008)","DOI":"10.46298\/dmtcs.3582"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: Short monotone formulae for the majority function. Journal of Algorithms\u00a05, 363\u2013366 (1984)","journal-title":"Journal of Algorithms"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Boppana, R.B.: Amplification of probabilistic boolean formulas. In: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 20\u201329 (1985)","DOI":"10.1109\/SFCS.1985.5"},{"issue":"1","key":"28_CR19","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF01202041","volume":"6","author":"A. Gupta","year":"1997","unstructured":"Gupta, A., Mahajan, S.: Using amplification to compute majority with small majority gates. Comput. Complex.\u00a06(1), 46\u201363 (1997)","journal-title":"Comput. Complex."},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0012-365X(90)90223-5","volume":"83","author":"P. Savicky","year":"1990","unstructured":"Savicky, P.: Random Boolean formulas representing any Boolean function with asymptotically equal probability. Discrete Mathematics\u00a083, 95\u2013103 (1990)","journal-title":"Discrete Mathematics"},{"key":"28_CR21","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1002\/rsa.20095","volume":"27","author":"A. Brodsky","year":"2005","unstructured":"Brodsky, A., Pippenger, N.: The boolean functions computed by random boolean formulas or how to grow the right function. Random Structures and Algorithms\u00a027, 490\u2013519 (2005)","journal-title":"Random Structures and Algorithms"},{"issue":"1-2","key":"28_CR22","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<103::AID-RSA5>3.0.CO;2-Z","volume":"10","author":"M. Drmota","year":"1997","unstructured":"Drmota, M.: Systems of functional equations. Random Structures and Algorithms\u00a010(1-2), 103\u2013124 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Lalley, S.P.: Finite range random walk on free groups and homogeneous trees. The Annals of Probability\u00a021 (1993)","DOI":"10.1214\/aop\/1176989012"},{"key":"28_CR24","unstructured":"Flajolet, P., Sedgewick, R.: Analytic combinatorics: Functional equations, rational and algebraic functions. Technical Report 4103, INRIA (January 2001)"},{"key":"28_CR25","volume-title":"Analytic Combinatorics","author":"P. Flajolet","year":"2008","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (to appear, 2008) Available from the authors\u2019 web page"},{"key":"28_CR26","unstructured":"Pivoteau, C., Salvy, B., Soria, M.: Combinatorial Newton iteration to compute Boltzmann oracle. Technical report, Journ\u00e9es AL\u00c9A (March 2008), http:\/\/www-calfor.lip6.fr\/pivoteau"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85238-4_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T16:58:45Z","timestamp":1684515525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85238-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540852377","9783540852384"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85238-4_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}