Jakub Kozik
-
Subcritical pattern languages for and/or trees
dmtcs:3582 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2008,
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
-
https://doi.org/10.46298/dmtcs.3582
Subcritical pattern languages for and/or treesArticle
Authors: Jakub Kozik 1
NULL
Jakub Kozik
1 Theoretical Computer Science Department [Krakow]
Let $P_k(f)$ denote the density of and/or trees defining a boolean function $f$ within the set of and/or trees with fixed number of variables $k$. We prove that there exists constant $B_f$ such that $P_k(f) \sim B_f \cdot k^{-L(f)-1}$ when $k \to \infty$, where $L(f)$ denote the complexity of $f$ (i.e. the size of a minimal and/or tree defining $f$). This theorem has been conjectured by Danièle Gardy and Alan Woods together with its counterpart for distribution $\pi$ defined by some critical Galton-Watson process. Methods presented in this paper can be also applied to prove the analogous property for $\pi$.
Antoine Genitrini;Cécile Mailler, Lecture Notes in Computer Science, Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem, pp. 466-477, 2014, omid:br/061402615007 doi:10.1007/978-3-642-54423-1_41.
Hervé Fournier;Danièle Gardy;Antoine Genitrini;Antoine Genitrini Bernhard Gittenberger, 2011, The fraction of large random trees representing a given Boolean function in implicational logic, Random Structures & Algorithms, 40, 3, pp. 317-349, omid:br/06190333042 doi:10.1002/rsa.20379.
Hervé Fournier;Danièle Gardy;Antoine Genitrini;Marek Zaionc, 2010, Tautologies over implication with negative literals, Mathematical Logic Quarterly, 56, 4, pp. 388-396, omid:br/061702678662 doi:10.1002/malq.200810053.
Hervé Fournier;Danièle Gardy;Antoine Genitrini;Bernhard Gittenberger, Lecture Notes in Computer Science, Complexity and Limiting Ratio of Boolean Functions over Implication, pp. 347-362, 2008, omid:br/062403085321 doi:10.1007/978-3-540-85238-4_28.