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

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 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.87-107
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990562
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:19:33
Dernière modification le : vendredi 17 novembre 2017 - 15:36:01
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:31:27

Fichier

1515-6903-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990562, version 1

Collections

Citation

Jason P. Bell, Stanley N. Burris, Karen A. Yeats. Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.87-107. 〈hal-00990562〉

Partager

Métriques

Consultations de la notice

47

Téléchargements de fichiers

142