The Strange Logic of Galton-Watson Trees
370 views · Published 22 June 2016 · 1:02:55 · Indexed 25 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
The Galton-Watson tree is a basic demographic model. The classic equation for a Galton-Watson tree being infinite has two solutions, only one of which is "correct." What about other properties. (Example: Some node has precisely two children.) We show that when the property is what is called first order than there is a unique solution to the corresponding equation. We consider "tree automata" and the situation for monadic second order properties.
