Some Typical Properties of Large AND/OR Boolean Formulas

Lefmann, H. - Savický, Petr
Some Typical Properties of Large AND/OR Boolean Formulas.
Random Structures and Algorithms. Roč. 10, č. 3 (1997), s. 337-351. ISSN 1042-9832. E-ISSN 1098-2418
Impakt faktor: 0.471, rok: 1997
http://hdl.handle.net/11104/0123578

Citováno: 25

--- BRODSKY, A. - PIPPENGER, N. The Boolean functions computed by random Boolean formulas OR how to grow the right function. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832, DEC 2005, vol. 27, no. 4, p. 490-519. [WOS]
--- KOSTRZYCKA, Z. On the Density of Truth of Locally Finite Logics. JOURNAL OF LOGIC AND COMPUTATION. ISSN 0955-792X, DEC 2009, vol. 19, no. 6, p. 1113-1125. [WOS]
--- MOZEIKA, A. - SAAD, D. - RAYMOND, J. Computing with Noise: Phase Transitions in Boolean Formulas. PHYSICAL REVIEW LETTERS. ISSN 0031-9007, DEC 11 2009, vol. 103, no. 24. [WOS]
--- FOURNIER, H. - GARDY, D. - GENITRINI, A. - GITTENBERGER, B. Complexity and limiting ratio of boolean functions over implication. MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008, PROCEEDINGS. ISSN 0302-9743, 2008, vol. 5162, p. 347-362. [WOS]
--- GENITRINI, A. - KOZIK, J. - ZAIONC, M. Intuitionistic vs. classical tautologies, quantitative comparison. TYPES FOR PROOFS AND PROGRAMS. ISSN 0302-9743, 2008, vol. 4941, p. 100-109. [WOS]
--- FOURNIER, H. - GARDY, D. - GENITRINI, A. - ZAIONC, M. Classical and intuitionistic logic are asymptotically identical. Computer Science Logic, Proceedings. ISSN 0302-9743, 2007, vol. 4646, p. 177-193. [WOS]
--- FOURNIER, H. - GARDY, D. - GENITRINI, A. - ZAIONC, M. Tautologies over implication with negative literals. MATHEMATICAL LOGIC QUARTERLY. ISSN 0942-5616, AUG 2010, vol. 56, no. 4, p. 388-396. [WOS]
--- FOURNIER, H. - GARDY, D. - GENITRINI, A. - GITTENBERGER, B. The fraction of large random trees representing a given Boolean function in implicational logic. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832, MAY 2012, vol. 40, no. 3, p. 317-349. [WOS]
--- GRYGIEL, K. - IDZIAK, P.M. - ZAIONC, M. How big is fragment of logic. JOURNAL OF LOGIC AND COMPUTATION. ISSN 0955-792X, JUN 2013, vol. 23, no. 3, p. 673-691. [WOS]
--- BROUTIN, N. - FLAJOLET, P. The distribution of height and diameter in random non-plane binary trees. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832, SEP 2012, vol. 41, no. 2, p. 215-252. [WOS]
--- GENITRINI, A. - GITTENBERGER, B. - KRAUS, V. - MAILLER, C. Probabilities of Boolean Functions Given by Random Implicational Formulas. ELECTRONIC JOURNAL OF COMBINATORICS. ISSN 1077-8926, JUN 6 2012, vol. 19, no. 2. [WOS]
--- MOZEIKA, A. - SAAD, D. - RAYMOND, J. Noisy random Boolean formulae: A statistical physics perspective. PHYSICAL REVIEW E. ISSN 1539-3755, OCT 14 2010, vol. 82, no. 4, 1. [WOS]
--- FLAJOLET, P. - SEDGEWICK, R. Analytic Combinatorics. ANALYTIC COMBINATORICS. 2009, p. 1-810. [WOS]
--- PEMANTLE, R. - WARD, M.D. Exploring the Average Values of Boolean Functions via Asymptotics and Experimentation. PROCEEDINGS OF THE EIGHTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS AND THE THIRD WORKSHOP ON ANALYTIC ALGORITHMICS AND COMBINATORICS. 2006, p. 253-262. [WOS]
--- CHAUVIN, B. - FLAJOLET, P. - GARDY, D. - GITTENBERGER, B. And/or trees revisited. COMBINATORICS PROBABILITY & COMPUTING. ISSN 0963-5483, JUL-SEP 2004, vol. 13, no. 4-5, SI, p. 475-497. [WOS]
--- GENITRINI, A. - GITTENBERGER, B. - KRAUS, V. - MAILLER, C. Associative and commutative tree representations for Boolean functions. THEORETICAL COMPUTER SCIENCE. ISSN 0304-3975, MAR 9 2015, vol. 570, p. 70-101. [WOS]
--- MOZEIKA, A. - SAAD, D. On Reliable Computation by Noisy Random Boolean Formulas. IEEE TRANSACTIONS ON INFORMATION THEORY. ISSN 0018-9448, JAN 2015, vol. 61, no. 1, p. 637-644. [WOS]
--- GENITRINI, A. - MAILLER, C. Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem. LATIN 2014: THEORETICAL INFORMATICS. ISSN 0302-9743, 2014, vol. 8392, p. 466-477. [WOS]
--- DE PANAFIEU, E. - GARDY, D. - GITTENBERGER, B. - KUBA, M. 2-Xor Revisited: Satisfiability and Probabilities of Functions. ALGORITHMICA. ISSN 0178-4617, DEC 2016, vol. 76, no. 4, p. 1035-1076. [WOS]
--- GENITRINI, A. - MAILLER, C. Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability. ALGORITHMICA. ISSN 0178-4617, DEC 2016, vol. 76, no. 4, p. 1106-1138. [WOS]
--- CHAUVIN, B. - GARDY, D. - MAILLER, C. A sprouting tree model for random boolean functions. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832, DEC 2015, vol. 47, no. 4, p. 635-662. [WOS]
--- BENDKOWSKI, M. - GRYGIEL, K. - ZAIONC, M. Asymptotic Properties of Combinatory Logic. THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015). ISSN 0302-9743, 2015, vol. 9076, p. 62-72. [WOS]
--- DAXNER, V. - GENITRINI, A. - GITTENBERGER, B. - MAILLER, C. THE RELATION BETWEEN TREE SIZE COMPLEXITY AND PROBABILITY FOR BOOLEAN FUNCTIONS GENERATED BY UNIFORM RANDOM TREES. APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS. ISSN 1452-8630, OCT 2016, vol. 10, no. 2, p. 408-446. [WOS]
--- BROUTIN, N. - MAILLER, C. And/or trees: A local limit point of view. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832, AUG 2018, vol. 53, no. 1, p. 15-58. [WOS]
--- BODINI, O. - GITTENBERGER, B. - GOLEBIEWSKI, Z. Enumerating lambda terms by weighted length of their De Bruijn representation. DISCRETE APPLIED MATHEMATICS. ISSN 0166-218X, APR 20 2018, vol. 239, p. 45-61. [WOS]