✦ LIBER ✦

Coloring rules for finite trees, and probabilities of monadic second order sentences

✍ Scribed by Alan R. Woods

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 296 KB
Volume: 10
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199707)10:4<453::aid-rsa3>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

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 is any monadic second-order sentence, then the fractions Ž . Ž . , of labeled and unlabeled rooted trees satisfying , 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 n ª ϱ.

📜 SIMILAR VOLUMES

Convergence of probabilities for the sec

Convergence of probabilities for the second order monadic properties of a random mapping

✍ Tomasz Łuczak; Luboš Thoma 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

We prove that the probability of each second order monadic property of a random mapping u converges as n ª ϱ.