Abstract:
T-decomposition is an algorithm that parses a finite string into a series of
parameters for a recursive string construction algorithm. Initially developed for
the communication of coding trees [18, 4], T-decomposition has since been studied
within the context of information measures. This involves the parsing of potentially
very large strings, which in turn requires algorithms with good time and space
complexity. This paper presents a T-decomposition algorithm with O(n log n) time
complexity.
