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 trees
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$.
Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: And/Or trees,probability distribution for Boolean functions,tree enumeration,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
7 Documents citing this article
Source : OpenCitations
Bendkowski, Maciej; Grygiel, Katarzyna; Zaionc, Marek, 2015, Asymptotic Properties Of Combinatory Logic, Lecture Notes In Computer Science, pp. 62-72, 10.1007/978-3-319-17142-5_7.
Broutin, Nicolas; Mailler, CĂŠcile, 2018, And/or Trees: A Local Limit Point Of View, Random Structures And Algorithms, 53, 1, pp. 15-58, 10.1002/rsa.20758.
Fournier, Hervé; Gardy, Danièle; Genitrini, Antoine; Zaionc, Marek, 2010, Tautologies Over Implication With Negative Literals, Zeitschrift Für Mathematische Logik Und Grundlagen Der Mathematik, 56, 4, pp. 388-396, 10.1002/malq.200810053.
Fournier, HervĂŠ; Gardy, Danièle; Genitrini, Antoine; Gittenberger, Bernhard, 2011, The Fraction Of Large Random Trees Representing A Given Boolean Function In Implicational Logic, Random Structures And Algorithms, 40, 3, pp. 317-349, 10.1002/rsa.20379.
Genitrini, Antoine; Kozik, Jakub, 2012, In The Full Propositional Logic, 5/8 Of Classical Tautologies Are Intuitionistically Valid, Annals Of Pure And Applied Logic, 163, 7, pp. 875-887, 10.1016/j.apal.2011.09.011.
Genitrini, Antoine; Mailler, CĂŠcile, 2014, Equivalence Classes Of Random Boolean Trees And Application To The Catalan Satisfiability Problem, LATIN 2014: Theoretical Informatics, pp. 466-477, 10.1007/978-3-642-54423-1_41.
Genitrini, Antoine; Mailler, CĂŠcile, 2016, Generalised And Quotient Models For Random And/Or Trees And Application To Satisfiability, Algorithmica, 76, 4, pp. 1106-1138, 10.1007/s00453-016-0113-3.