Authors: | Astola, Jaakko Astola, Pekka Stanković, Radomir Tabus, Ioan |

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

Journal: | Journal of Multiple-Valued Logic and Soft Computing |

Volume: | 31 |

Issue: | 3 |

First page: | 239 |

Last page: | 253 |

Issue Date: | 1-Jan-2018 |

Rank: | M22 |

ISSN: | 1542-3980 |

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

Publisher: | Old City Publishing |

Show full item record

#### SCOPUS^{TM}

Citations

1
checked on Nov 4, 2024

#### Page view(s)

13
checked on Nov 4, 2024

#### Google Scholar^{TM}

Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.