Coloring rules for finite trees, and probabilities of monadic second order sentences
Coloring rules for finite trees, and probabilities of monadic second order sentences
复制标题
有限树的着色规则和一元二阶句子的概率
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Alan R. Woods
中科院分区：
文献类型：
--
作者：
Alan R. Woods
着色规则系统是一组用于对任何有限根树的顶点进行着色的规则，从其叶子开始，其具有以下属性：分配给每个顶点的颜色仅取决于每种颜色的直接前辈的数量。研究了具有给定根颜色的 n 个顶点树的部分的渐近行为。作为主要应用，如果 w 是任何一元二阶句子，则分数 Ž 。 Ž 。 m w , n w 满足 w 的标记和未标记有根树，收敛到限制 n n 概率。这个想法的扩展表明，对于 k 个变量（k 固定）的布尔公式的特定模型，计算给定布尔函数的大小为 n 的此类公式的分数接近正极限 na`。 Q 1997 约翰·威利父子公司 (John Wiley & Sons, Inc.) Ž .随机结构。阿尔格., 10, 453]485 1997
A system of coloring rules is a set of rules for coloring the vertices of any finite rooted tree, starting at its leaves, which has the property that the color assigned to each vertex depends only on how many of its immediate predecessors there are of each color. The asymptotic behavior of the fraction of n vertex trees with a given root color is investigated. As a primary application, if w is any monadic second-order sentence, then the fractions Ž . Ž . m w , n w of labeled and unlabeled rooted trees satisfying w, converge to limiting n n probabilities. An extension of the idea shows that for a particular model of Boolean formulas in k variables, k fixed, the fraction of such formulas of size n which compute a given Boolean function approaches a positive limit as na`. Q 1997 John Wiley & Sons, Inc. Ž . Random Struct. Alg., 10, 453]485 1997