ITERATION OF INVERTIBLE TRANSDUCTIONS

We study iterated transductions defined by a class of invertible Mealy automata over the binary alphabet. It is shown that in some cases the resulting orbit relation is rational and we determine the complexity of several natural computational problems associated with the iterated transductions. In particular, we show how to compute timestamps and coordinates.