Tampere University of Technology

TUTCRIS Research Portal

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

Research output: Contribution to journalArticleScientificpeer-review

Standard

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

In: Journal of Multiple-Valued Logic and Soft Computing, Vol. 31, No. 3, 2018, p. 239-253.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Astola, J, Astola, P, Stanković, R & Tabus, I 2018, 'An algebraic approach to reducing the number of variables of incompletely defined discrete functions', Journal of Multiple-Valued Logic and Soft Computing, vol. 31, no. 3, pp. 239-253.

APA

Astola, J., Astola, P., Stanković, R., & Tabus, I. (2018). An algebraic approach to reducing the number of variables of incompletely defined discrete functions. Journal of Multiple-Valued Logic and Soft Computing, 31(3), 239-253.

Vancouver

Astola J, Astola P, Stanković R, Tabus I. An algebraic approach to reducing the number of variables of incompletely defined discrete functions. Journal of Multiple-Valued Logic and Soft Computing. 2018;31(3):239-253.

Author

Astola, Jaakko ; Astola, Pekka ; Stanković, Radomir ; Tabus, Ioan. / An algebraic approach to reducing the number of variables of incompletely defined discrete functions. In: Journal of Multiple-Valued Logic and Soft Computing. 2018 ; Vol. 31, No. 3. pp. 239-253.

Bibtex - Download

@article{f5f9383038674e16af2018db8f8f0d31,
title = "An algebraic approach to reducing the number of variables of incompletely defined discrete functions",
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.",
author = "Jaakko Astola and Pekka Astola and Radomir Stanković and Ioan Tabus",
note = "EXT={"}Stanković, Radomir{"}",
year = "2018",
language = "English",
volume = "31",
pages = "239--253",
journal = "Journal of Multiple-Valued Logic and Soft Computing",
issn = "1542-3980",
publisher = "Old City Publishing",
number = "3",

}

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 -