Discrete Mathematics & Theoretical Computer Science, Vol 14, No 1 (2012)

Font Size:  Small  Medium  Large

Monadic second-order classes of forests with a monadic second-order 0-1 law

Jason P. Bell, Stanley N. Burris, Karen Yeats

Abstract


Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence ρ. If ρ≥1 then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and (≥n). Using this, one has an explicit expression for T(x) in terms of the initial functions x and x·&big;(1-xn)-1, the operations of addition and multiplication, and the Pólya exponentiation operators En, E(≥n). Let F be a monadic-second order class of finite forests, and let F(x)=∑n f(n) xn be its (ordinary) generating function. Suppose F is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class T of trees in F, Compton's theory of 0-1 laws, and a significantly strengthened version of 2003 results of Bell and Burris on generating functions, we show that F has a monadic second-order 0-1 law iff the radius of convergence of F(x) is 1 iff the radius of convergence of T(x) is ≥1.

Full Text: PDF PostScript