Group Theory of the Kolakoski Sequence

Run-length decoding is an operation on sequences in which a positive integer $a$ is replaced by a run(sequence of repeated elements) of length $a$. Iterated run-length decodings applied to sequences with alphabets consisting of pairs of positive integers $\{p,q\}$ have attracted attention from mathematicians, most notably in their role defining the well-known Kolakoski sequence. $n$-th-iterated run-length decodings are controlled by naturally associated permutation automata $A_n^{p,q}$. Here we study the transformation groups ${\mathcal{K}}_n^{p,q}$ of these automata. They are subgroups of the automorphism group of binary trees of depth $n+1$. They are naturally subgroups of(and likely equal to) a certain group ${\mathcal{J}}_n^{p,q}$ with an intricate recursive structure; their limit group is plausibly weakly regular branch. As an application we determine the number of maximal-length orbits of the automata given an arbitrary input sequence for odd $n$.