BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Tree shift entropy Petersen, Karl


In joint work with Ibrahim Salama, we study the complexity function $p_\tau(n)$ of a labeled tree or tree shift, which counts as a function of $n$ the number of different labelings of a shape of size $n$. We give a definition of entropy, prove that the limit in the definition exists, and that the limit is the infimum. For tree shifts determined by adjacency constraints a version of Pavlov's strip technique proves strict inequality with dimension and provides an efficient approximation method. Attractive questions concern equilibrium measures and relations with other kinds of entropy.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International