Title of article
MSO zero-one laws on random labelled acyclic graphs Original Research Article
Author/Authors
Gregory L. McColm، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2002
Pages
17
From page
331
To page
347
Abstract
We use Ehrenfeucht-type games to prove that Monadic Second Order logic admits labelled zero-one laws for random free trees, generating the complete almost sure theory. Our method will be to dissect random trees to get a picture of what almost all random free trees look like. We will use elementary (second moment) methods to obtain probability results.
Keywords
Monadic second-order zero-one laws , Random labelled trees , Second moment method , Second-order Fraisse–Ehrenfeucht games
Journal title
Discrete Mathematics
Serial Year
2002
Journal title
Discrete Mathematics
Record number
950159
Link To Document