Mathematics – Logic
Scientific paper
2010-04-07
Mathematics
Logic
18 pages
Scientific paper
Let $\cT$ be a monadic-second order class of finite trees, and let $\bT(x)$ be its (ordinary) generating function, with radius of convergence $\rho$. If $\rho \ge 1$ then $\cT$ has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators $(n)$ and $(\ge n)$. Using this, one has an explicit expression for $\bT(x)$ in terms of the initial functions $x$ and $x\cdot \big(1-x^n\big)^{-1}$, the operations of addition and multiplication, and the P\'olya exponentiation operators $\sE_n, \sE_{\ge n}$. Let $\cF$ be a monadic-second order class of finite forests, and let $\bF(x)=\sum_n f(n) x^n$ be its (ordinary) generating function. Suppose $\cF$ is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class $\cT$ of trees in $\cF$, 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 $\cF$ has a monadic second-order 0--1 law iff the radius of convergence of $\bF(x)$ is 1 iff the radius of convergence of $\bT(x)$ is $\ge 1$.
Bell Jason
Burris Stanley
Yeats Karen
No associations
LandOfFree
Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-397782