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