Decomposition of Boolean Relations and Functions in Logic Synthesis and Data Analysis

Document Type

Chapter

Publication Date

2-5-2002

Publication Title

Rough Sets and Current Trends in Computing: Second International Conference, RSCTC 2000 Banff, Canada, October 16-19, 2000 Revised Papers

Publisher

Springer

Publisher Location

Berlin, Heidelberg

Edition

2001

First page number:

487

Last page number:

494

Abstract

This paper shows that the problem of decomposing a finite function f(A, B) into the form h (g(A), B), where g is a Boolean function, can be resolved in polynomial time, with respect to the size of the problem. It is also shown that omission of the characteristic of the g function can significantly complicate the problem. Such a general problem belongs to the N P-hard class of problems. The work shows how the problem of decomposition of a finite function can be reduced to the problem of coloring the vertices of a graph. It is also shown that the problem of decomposition of relations can be reduced to coloring the vertices of their hypergraphs. In order to prove the validity of the theorems, combinatory properties of Helly are used.

Keywords

Computer algorithms; Decomposition method

Disciplines

Computer Engineering | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or use interlibrary loan to garner a copy of the article. Publisher copyright policy allows author to archive post-print (author’s final manuscript). When post-print is available or publisher policy changes, the article will be deposited


Share

COinS