Subcritical pattern languages for and/or trees
Subcritical pattern languages for and/or trees
复制标题
和/或树的亚临界模式语言
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Kozik
中科院分区：
文献类型：
--
作者：
J. Kozik
设P_k（f）$表示定义布尔函数f$的与/或树在具有固定数目的变量k$的与/或树的集合内的密度。本文证明了存在常数B_f使得当k时P_k（f）sim B_f cdot k^{-L（f）-1} 其中$L（f）$表示$f$的复杂度（即定义$f$的最小和/或树的大小）。这个定理已经由Daniele Gardy和Alan Woods与它的对应物一起被证明了对于由一些临界Galton-Watson过程定义的分布$pi$。本文提出的方法也可用于证明$pi$的类似性质。
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 o 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 Daniele 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$.