TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko2016 IEEE 46th International Symposium on Multiple-Valued Logic, ISMVL 2016
KustantajaIEEE
Sivut107-112
Sivumäärä6
ISBN (elektroninen)9781467394888
DOI - pysyväislinkit
TilaJulkaistu - 18 heinäkuuta 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaIEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC -
Kesto: 1 tammikuuta 1900 → …

Julkaisusarja

Nimi
ISSN (elektroninen)2378-2226

Conference

ConferenceIEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC
Ajanjakso1/01/00 → …

Tiivistelmä

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. 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 > 2logq|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.

!!ASJC Scopus subject areas

Tutkimusalat

Julkaisufoorumi-taso