JUCS - Journal of Universal Computer Science 11(6): 1083-1101, doi: 10.3217/jucs-011-06-1083
A Fast T-decomposition Algorithm
expand article infoJia Yang‡, Ulrich Speidel‡
‡ Department of Computer Science, The University of Auckland, Auckland, New Zealand

Corresponding author: Jia Yang ( jyan055@cs.auckland.ac.nz )

© Jia Yang, Ulrich Speidel.
This article is freely available under the J.UCS Open Content License.
Citation: Yang J, Speidel U (2005) A Fast T-decomposition Algorithm. JUCS - Journal of Universal Computer Science 11(6): 1083-1101. https://doi.org/10.3217/jucs-011-06-1083
Open Access
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, parsing, entropy