## An algebraic approach to reducing the number of variables of incompletely defined discrete functions

Research output: Contribution to journal › Article › Scientific › peer-review

### Standard

**An algebraic approach to reducing the number of variables of incompletely defined discrete functions.** / Astola, Jaakko; Astola, Pekka; Stanković, Radomir; Tabus, Ioan.

Research output: Contribution to journal › Article › Scientific › peer-review

### Harvard

*Journal of Multiple-Valued Logic and Soft Computing*, vol. 31, no. 3, pp. 239-253.

### APA

*Journal of Multiple-Valued Logic and Soft Computing*,

*31*(3), 239-253.

### Vancouver

### Author

### Bibtex - Download

}

### RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - An algebraic approach to reducing the number of variables of incompletely defined discrete functions

AU - Astola, Jaakko

AU - Astola, Pekka

AU - Stanković, Radomir

AU - Tabus, Ioan

N1 - EXT="Stanković, Radomir"

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

M3 - Article

VL - 31

SP - 239

EP - 253

JO - Journal of Multiple-Valued Logic and Soft Computing

JF - Journal of Multiple-Valued Logic and Soft Computing

SN - 1542-3980

IS - 3

ER -