MSO zero-one laws on random labelled acyclic graphs
type: Item
instance of: scholarly article
title: MSO zero-one laws on random labelled acyclic graphs
zbMATH Open document ID: 1011.03022
DOI: 10.1016/S0012-365X(01)00375-2
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: In his paper ``Colouring rules for finite trees, and probabilities of monadic second order sentences'' [Random Struct. Algorithms 10, 453-485 (1997; Zbl 0872.03021)], \textit{A. R. Woods} showed that, for every sentence \(\varphi\) of monadic second-order logic, the labelled asymptotic probability of models of \(\varphi\) relative to the class of trees, i.e., of acyclic and connected graphs, exists. In the paper under review, a proof of this fact based on Ehrenfeucht-type games is presented.
reviewed by: Jörg Flum
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1792467
zbMATH Keywords: random labelled trees
zbMATH Keywords: zero-one laws
zbMATH Keywords: Ehrenfeucht games
author: Gregory Loren McColm
MaRDI profile type: Publication
Recommended article: Zero-One Laws for Sparse Random Graphs
Recommended article: Q4242579
Recommended article: Zero-one laws for random \(k\)-partite graphs
Recommended article: Zero-one laws for random graphs with vertices in a Boolean cube
Recommended article: On a sequence of random distance graphs subject to the zero-one law
Recommended article: Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\)
Recommended article: Q3123117
Recommended article: First-order zero-one law for the uniform model of the random graph
description: scientific article; zbMATH DE number 1792467