Geodesic
Subcritical pattern languages for and/or trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008).

Voir la notice de l'article provenant de la source Episciences

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$. 
@article{DMTCS_2008_special_254_a28,
     author = {Kozik, Jakub},
     title = {Subcritical pattern languages for and/or trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science},
     year = {2008},
     doi = {10.46298/dmtcs.3582},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3582/}
}
TY  - JOUR
AU  - Kozik, Jakub
TI  - Subcritical pattern languages for and/or trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2008
VL  - DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3582/
DO  - 10.46298/dmtcs.3582
LA  - en
ID  - DMTCS_2008_special_254_a28
ER  - 
%0 Journal Article
%A Kozik, Jakub
%T Subcritical pattern languages for and/or trees
%J Discrete mathematics & theoretical computer science
%D 2008
%V DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3582/
%R 10.46298/dmtcs.3582
%G en
%F DMTCS_2008_special_254_a28
Kozik, Jakub. Subcritical pattern languages for and/or trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008). doi : 10.46298/dmtcs.3582. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3582/

Cité par Sources :