Invertible transducers, iteration and coordinates

We study natural computational problems associated with iterated transductions defined by a class of invertible transducers over the binary alphabet. The transduction semigroups of these automata are known to be free Abelian groups and the orbits of words can be described as affine subspaces in a suitable geometry defined by the generators of these groups. We show how to compute the associated coordinates of words in quadratic time and how to apply coordinates to the problem of deciding whether two words generate the same orbit under a given transduction. In some special cases our algorithms can be implemented on finite state machines.