Multiple-Valued Index Generation Functions: Reduction of Variables by Linear Transformation
Tsutomu Sasao
We consider incompletely specified multiple-valued input index generation functions f : D → {1, 2, . . . , k}, where D ⊆ Pn and 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 2 logp(k + 1) or fewer variables, when k is sufficiently smaller than Pn. 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.