TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Standard

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

julkaisussa: Journal of Multiple-Valued Logic and Soft Computing, Vuosikerta 31, Nro 3, 2018, s. 239-253.

Tutkimustuotosvertaisarvioitu

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, Vuosikerta. 31, Nro 3, Sivut 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. Julkaisussa: Journal of Multiple-Valued Logic and Soft Computing. 2018 ; Vuosikerta 31, Nro 3. Sivut 239-253.

Bibtex - Lataa

@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) - Lataa

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 -