# 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$.
Keywords :
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.437-448, 2008, DMTCS Proceedings
Domaine :
Liste complète des métadonnées

Littérature citée [9 références]

https://hal.inria.fr/hal-01194664
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:47
Dernière modification le : mercredi 10 mai 2017 - 17:41:17
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:51:58

### Fichier

dmAI0129.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01194664, version 1

### Citation

Jakub Kozik. Subcritical pattern languages for and/or trees. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.437-448, 2008, DMTCS Proceedings. 〈hal-01194664〉

### Métriques

Consultations de la notice

## 90

Téléchargements de fichiers