On Homogeneous Segments

摘要

Properties of homogeneous segment sets are investigated in this paper. A universal characterization of homogeneous sets is preented in the form of a polynomial algorithm which decides whether or not a set S is homogeneous with respect to S~*. It is shown that any set of homogeneous segments can be reduced to the uniquely determined minimal base and a polynomial algorithm solving this task is presented as well. Further, an efficient algorithm for finding the segment representation of a word by homogeneous segments is provided.