Skip to Main content Skip to Navigation
Conference papers

Subcritical pattern languages for and/or trees

Abstract : 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$.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01194664
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, September 7, 2015 - 12:50:47 PM
Last modification on : Wednesday, May 10, 2017 - 5:41:17 PM
Long-term archiving on: : Tuesday, December 8, 2015 - 12:51:58 PM

File

dmAI0129.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01194664, version 1

Collections

Citation

Jakub Kozik. Subcritical pattern languages for and/or trees. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. pp.437-448. ⟨hal-01194664⟩

Share

Metrics

Record views

122

Files downloads

554