MSO 0-1 law for recursive random trees

2020/07/29 by Yury Malyshkin, Malyshkin, Y. A., Maksim Zhukovskii +1 · 1 citation
Computer Science · Mathematics · #05C80 #Complexity and Algorithms in Graphs #Distributed systems and fault tolerance #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2007.14768

openalex publication_date 2020/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.

Cited by

• Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words

Related

• Random recursive trees and preferential attachment trees are random\n split trees
• On asymptotics of two non-uniform recursive tree models
• Estimating the history of a random recursive tree
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Some remarks on biased recursive trees