### 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-x^{n})^{-1}, the operations of addition and multiplication, and the Pólya exponentiation operators E_{n}, E_{(≥n)}. Let F be a monadic-second order class of finite forests, and let**F**(x)=∑_{n}f(n) x^{n}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