Subcritical pattern languages for and/or trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2008

Subcritical pattern languages for and/or trees

Résumé

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$.
Fichier principal
Vignette du fichier
dmAI0129.pdf (239.55 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01194664 , version 1 (07-09-2015)

Identifiants

Citer

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

Collections

TDS-MACS
73 Consultations
484 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More