# Iterated Parity Complexity

I wondered if anyone knew the complexity of the following problem 'Iterated Parity' (that has come up looking at the Grigorchuk group word problem).

Define the mapping $$\phi : \{0,1\}^* \rightarrow \{0,1\}^*$$ as follows. Let $$w \in \{0,1\}^*$$ be a prefix of an input, and let $$a \in \{0,1\}$$ be the symbol that comes after $$w$$. Then $$\phi$$ maps $$a$$ to 0 if $$a = 0$$ and the number of 1's in $$w$$ is even, and $$\phi$$ maps $$a$$ to 1 if $$a = 0$$ and the number of 1's in $$w$$ is odd. And $$\phi$$ maps $$a$$ to the empty string if $$a$$ is 1.

For example $$\phi(010110) = 011$$.

Define $$\phi^k = \phi (\phi^{k-1} (x) )$$

As input you are given a string $$x \in \{0,1\}^n$$, and a parameter k. The problem is determining if $$\phi^k(x)$$ has an even number of 1s or an odd number.

For k constant, this is just basically parity so its in $$NC1$$. For general k, an easy upper bound is $$NC^2$$. An upper bound of logspace holds as well. Can we say anything stronger about this problem? It would surprise me if this problem was in $$NC1$$ though I guess it might be possible. I lean towards hardness for logspace but I'm not sure how to show that.