Multiple-Valued Index Generation Functions: Reduction of Variables by Linear Transformation
TSUTOMU SASAO We consider incompletely specified multiple-valued input index generation functions f : P = {0, 1, 2, . . . , p − 1}. In such functions, the number of variables to represent f can be often reduced. Let k be the number of elements in D. We show that most functions can be represented with 2log(_{p}k + 1) or fewer variables, when k is sufficiently smaller than P. Also, to further reduce the number of variables, we use linear transformations. To find good linear transformations, we introduce the imbalance measure and the ambiguity measure. A heuristic algorithm to reduce the number of variables by linear transformation is presented. Experimental results using randomly generated functions and lists of English words are shown.^{n} |
|||