Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

Abstract: Let

c T

be a monadic-second order class of finite trees, and let

be its (ordinary) generating function, with radius of convergence

h o

. If

h o g e 1

then

c T

has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators

(n)

and

(g e n)

. Using this, one has an explicit expression for

in terms of the initial functions

x

and

, the operations of addition and multiplication, and the P'olya exponentiation operators

s E_{n}, s E_{g e n}

. Let

c F

be a monadic-second order class of finite forests, and let

be its (ordinary) generating function. Suppose

c F

is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class

c T

of trees in

c 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

c F

has a monadic second-order 0--1 law iff the radius of convergence of

is 1 iff the radius of convergence of

is

g e 1

.

Recommendations

Cited in

(1)

This page was built for publication: Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law