Name
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 > 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ISMVL.2016.18 | 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL) |
Keywords | DocType | Volume |
multiple valued functions,index generation functions,reduction of variables | Journal | 31 |
Issue | ISSN | ISBN |
SP3 | 1542-3980 | 978-1-4673-9490-1 |
Citations | PageRank | References |
6 | 0.59 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jaakko Astola | 1 | 1515 | 230.41 |
| Pekka Astola | 2 | 20 | 4.98 |
| Radomir S. Stankovic | 3 | 188 | 47.07 |
| Ioan Tabus | 4 | 276 | 38.23 |