TR04-057 Authors: Monica del Pilar Canales Chacon, Michael Johannes Vielhaber

Publication: 15th July 2004 17:45

Downloads: 934

Keywords:

{\bf Abstract}

Isometries on formal power series over the finite field $\ff_2$

or on $2$--adic integers can be

computed by invertible transducers on inputs from $\{0,1\}^\infty$.

We consider the structural complexity of an isometry $f$,

measured as {\it tree complexity} $T(f,h)$, $h$ the tree height

[H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, 12 (1996)]

and the computational complexity, as {\it number of bit operations}

$B(f,n)$ needed for the first $n$ input / output symbols.

We introduce the shift commutator

$\SC(f) := \sigma^{-1}\circ f^{-1}\circ \sigma\circ f$ ($\sigma$ the shift on

$\{0,1\}^\infty$)

and show\ \

that $f\mapsto \SC(f)$ is a selfmap on the set of all isometries.

We obtain the polynomial bounds $T(\SC(f),h) \leq T(f,h)^2 - T(f,h) + 2$

and $B(f,n) \leq n\cdot B(\SC(f),n))$, by simulating $f$ by $n$ copies of

$\SC$.

On the other hand, trying to bound $T(f,h)$ by $T(\SC(f),h)$

it turns out that {\it e.g.} for the isometries

connected to the continued fraction expansion and

to Collatz' 3N+1 conjecture, the function $f$ itself is structurally

{\it exponentially} more complex than its $\SC(f)$. Hence simulating $f$ by

$\SC(f)$ may yield sharper upper bounds for the bit complexity as can be

inferred from $f$ alone.

We finish with some dynamical aspects of isometries like orbits, ergodicity,

preservation of measure.