Probabilistic equivalence checking of multiple-valued functions
2004 (English)In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 10, no 4, 395-414 p.Article in journal (Refereed) Published
This paper describes a probabilistic method for verifying the equivalence of two multiple-valued functions. Each function is hashed to an integer code by transforming it to a integer-valued polynomial and evaluating it for values of variables taken independently and uniformly at random from a finite field. Since the polynomial is unique for a given function, if two hash codes are different, then the functions are not equivalent. However, if two hash codes are the same, the functions may or may not be equivalent, because different polynomials may happen to hash to the same code. Thus, the method presented in this paper determines the equivalence of two functions with a known (small) probability of error, arising from collisions between inequivalent functions. Such a method seems to be an attractive alternative for verifying functions that are too large to be handled by deterministic equivalence checking methods.
Place, publisher, year, edition, pages
2004. Vol. 10, no 4, 395-414 p.
multiple-valued function, equivalence checking, probabilistic verification
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-24000ISI: 000226608500005ScopusID: 2-s2.0-7044235205OAI: oai:DiVA.org:kth-24000DiVA: diva2:342699
QC 201005252010-08-102010-08-102016-05-09Bibliographically approved