An algebraic approach to reducing the number of variables of incompletely defined discrete functions
Research output: Contribution to journal › Article › Scientific › peer-review
Details
| Original language | English |
|---|---|
| Pages (from-to) | 239-253 |
| Number of pages | 15 |
| Journal | Journal of Multiple-Valued Logic and Soft Computing |
| Volume | 31 |
| Issue number | 3 |
| Publication status | Published - 2018 |
| Publication type | A1 Journal article-refereed |
Abstract
In this paper, we consider incompletely defined discrete functions, i.e., Boolean and multiple-valued functions, f : S → {0, 1, . . . , q - 1} where S ⊆ {0, 1, . . . , q - 1}n i.e., the function value is specified only on a certain subset S of the domain of the corresponding completely defined function. We assume the function to be sparse i.e. |S| is 'small' relative to the cardinality of the domain. We show that by embedding the domain {0, 1, . . . , q - 1}n , where n is the number of variables and q is a prime power, in a suitable ring structure, the multiplicative structure of the ring can be used to construct a linear function {0, 1, . . . , q - 1}n → {0, 1, . . . , q - 1}m that is injective on S provided that m > 2 logq |S| + logq (n - 1). In this way we find a linear transform that reduces the number of variables from n to m, and can be used e.g. in implementation of an incompletely defined discrete function by using linear decomposition.