COLORING RULES FOR FINITE TREES, AND PROBABILITIES OF MONADIC 2ND-ORDER SENTENCES

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 prop erty that the color assigned to each vertex depends only on how many o f its immediate predecessors there are of each color. The asymptotic b ehavior of the fraction of n vertex tries with a given root color is i nvestigated. As a primary application, if phi is any monadic second-or der sentence, then the fractions mu(n)(phi), nu(n)(phi) of labeled and unlabeled rooted trees satisfying phi, converge to limiting probabili ties. An extension of the idea shows that for a particular model of Bo olean 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 n --> infinity. (C) 1997 John Wiley & Sons, Inc.