Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Probabilistic equivalence checking of multiple-valued functions
KTH, Superseded Departments, Electronic Systems Design.ORCID iD: 0000-0001-7382-9408
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
Abstract [en]

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.
Keyword [en]
multiple-valued function, equivalence checking, probabilistic verification
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-24000ISI: 000226608500005Scopus ID: 2-s2.0-7044235205OAI: oai:DiVA.org:kth-24000DiVA: diva2:342699
Note

QC 20100525

Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Scopus

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Dubrova, Elena
By organisation
Electronic Systems Design
In the same journal
Journal of Multiple-Valued Logic and Soft Computing
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 56 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf