A Fast T-decomposition Algorithm

Jia Yang (Department of Computer Science, The University of Auckland, New Zealand)

Ulrich Speidel (Department of Computer Science, The University of Auckland, New Zealand)

Abstract: T-decomposition was first proposed and implemented as an algorithm by Mark Titchener. It has applications in communication of code sets and in the fields of entropy and similarity measurement. The first implementation of a T-decomposition algorithm by Titchener was subsequently followed by a faster version named tcalc, developed in conjunction with Scott Wackrow. An improved T-decomposition algorithm was published in 2003 by the authors with the implementation tlist. This paper introduces a new algorithm that builds on our 2003 algorithm. Comparative experimental results are given to show that the new version has a significantly better time performance than previous algorithms.

Keywords: T-decomposition, computable complexity measures, entropy, parsing

Categories: E.4