MSO zero-one laws on random labelled acyclic graphs (Q1613549)

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.