The Strange Logic of Galton-Watson Trees

Опубликовано 22 июня 2016, 19:21

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.