Event
Moumanti Podder, Courant Institute
Thursday, January 26, 2017 16:30to17:30
Burnside Hall
room 1205, 805 rue Sherbrooke Ouest, Montreal, QC, H3A 0B9, CA
The Strange Logic of Galton-Watson Trees
This talk will focus on probabilities of first order (FO) and existential monadic second order (EMSO) sentences on the Galton-Watson (GW) tree. I shall limit myself to Poisson offspring distributions, though many of the results can be extended to very general distributions. Fix $k in mathbb{N}$. Conditioned on survival of the tree, we show that all FO sentences of quantifier depth k are determined by a local neighbourhood of the root (of radius $approx 3^{k+2}$). We devise a recursive procedure to compute these probabilities, conditioned on the tree's survival. The probabilities are very nice functions of $lambda$ and $p_{lambda}$, the survival probability. Using Ehrenfeucht games and corresponding equivalence classes, we show that the probability of any FO sentence is analytic in $lambda$.
I shall discuss some of our ongoing work: rogue solutions, i.e. solutions of equations derived from tree automata that do not admit any interpretation; an example of a sentence that is not expressible almost surely as an EMSO, etc. I shall end with speculations and conjectures that hopefully the audience will find fascinating.
I shall discuss some of our ongoing work: rogue solutions, i.e. solutions of equations derived from tree automata that do not admit any interpretation; an example of a sentence that is not expressible almost surely as an EMSO, etc. I shall end with speculations and conjectures that hopefully the audience will find fascinating.