Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SHIFT COMMUTATOR:
Reports tagged with shift commutator:
TR04-057 | 16th May 2004
Monica del Pilar Canales Chacon, Michael Johannes Vielhaber

#### Structural and Computational Complexity of Isometries and their Shift Commutators

{\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.}, ... more >>>

ISSN 1433-8092 | Imprint