Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TREE COMPLEXITY:
Reports tagged with tree complexity:
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