Change search
ReferencesLink to record
Permanent link

Direct link
A polynomial time algorithm for non-disjoint decomposition of multiple-valued functions
KTH, Superseded Departments, Electronic Systems Design.ORCID iD: 0000-0001-7382-9408
2004 (English)In: 34th International Symposium On Multiple-Valued Logic, Proceedings, 2004, 309-314 p.Conference paper (Refereed)
Abstract [en]

This paper addresses the problem of non-disjoint decomposition of multiple-valued functions. First, we show that the problem of computing non-disjoint decompositions of a multiple-valued function is related to the problem of finding multiple-vertex dominators of a logic circuit, representing the function. Second, we present an O(n(k)) algorithm for computing all multiple-vertex dominators of a fixed size k, where n is the number of gates of the logic circuit. Our result is important because no polynomial-time algorithm for finding all possible non-disjoint decompositions of multiple-valued functions is known. The presented approach allows us computing a certain subset of non-disjoint decompositions (all reflected in a given circuit structure) in polynomial time. A set of experiments on benchmark circuits illustrates the efficiency of our approach.

Place, publisher, year, edition, pages
2004. 309-314 p.
, International Symposium on Multiple-Valued Logic, ISSN 0195-623X
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-44377ISI: 000222045600049ScopusID: 2-s2.0-3142672251ISBN: 0-7695-2130-4OAI: diva2:450622
34th International Symposium on Multiple-Valued Logic (ISMVL 2004) Location: Univ Toronto, Toronto, Canada, Date: MAY 19-22, 2004

QC 20111021

Available from: 2011-10-21 Created: 2011-10-20 Last updated: 2016-06-08Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Dubrova, Elena
By organisation
Electronic Systems Design
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 37 hits
ReferencesLink to record
Permanent link

Direct link