Jason P. Bell ; Stanley N. Burris ; Karen A. Yeats - Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

dmtcs:566 - Discrete Mathematics & Theoretical Computer Science, May 8, 2012, Vol. 14 no. 1 - https://doi.org/10.46298/dmtcs.566
Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

Authors: Jason P. Bell 1; Stanley N. Burris 2; Karen A. Yeats 1

  • 1 Department of Mathematics [Burnaby]
  • 2 Department of Pure Mathematics [Waterloo]

Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence rho. If rho >= 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 . (1 - x(n))(-1), the operations of addition and multiplication, and the Polya exponentiation operators E-n, E-(>= n). Let F be a monadic-second order class of finite forests, and let F (x) = Sigma(n) integral(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.

Volume: Vol. 14 no. 1
Section: Automata, Logic and Semantics
Published on: May 8, 2012
Accepted on: June 9, 2015
Submitted on: April 1, 2010
Keywords: Trees,forests,monadic second-order class,ordinary generating function,radius of convergence,Compton equations,0-1 law,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1090/s0002-9947-03-03299-9
  • 10.1090/s0002-9947-03-03299-9
  • 10.1090/s0002-9947-03-03299-9
Asymptotics for logical limit laws: When the growth of the components is in an RT class

Consultation statistics

This page has been seen 245 times.
This article's PDF has been downloaded 254 times.