DECOMPOSABILITY OF PARTIALLY DEFINED BOOLEAN FUNCTIONS

被引：22

作者：

BOROS, E

GURVICH, V

HAMMER, PL

IBARAKI, T

KOGAN, A

机构：

[1] RUTGERS STATE UNIV,RUTCOR,NEW BRUNSWICK,NJ 08903

[2] KYOTO UNIV,FAC ENGN,DEPT APPL MATH & PHYS,KYOTO 606,JAPAN

[3] RUTGERS STATE UNIV,FAC MANAGEMENT,NEW BRUNSWICK,NJ 08903

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 62卷 / 1-3期

关键词：

D O I：

10.1016/0166-218X(94)00145-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The problem of recognizing decomposability of partially defined Boolean functions is considered. The results include polynomial time algorithms for certain important types of decomposition, as well as NP-completeness proofs for more complex structures.

引用

页码：51 / 75

页数：25

共 21 条

[1] COMPOSITIONAL COMPLEXITY OF BOOLEAN FUNCTIONS [J].

ABELSON, H ;

EHRENFEUCHT, A ;

FICKETT, J ;

MYCIELSKI, J .

DISCRETE APPLIED MATHEMATICS, 1982, 4 (01) :1-10

[2]

Adventures R. L., 1957, P INT S THEOR SWITCH, P74

[3]

APSWALL B, 1979, INFORM PROCESS LETT, V8, P121

[4]

BIOCH JC, IN PRESS DISCRETE MA

[5]

BOROS E, 1994, DIMACS949 RUTG U TEC

[6]

BRAYTON RK, 1990, P IEEE, V78

[7]

Crama Y., 1988, Annals of Operations Research, V16, P299, DOI 10.1007/BF02283750

[8]

CRIST SC, 1980, IEEE T COMPUT, V29, P1013, DOI 10.1109/TC.1980.1675497

[9] DECOMPOSING A RELATION INTO A TREE OF BINARY RELATIONS [J].

DECHTER, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (01) :2-24

[10] STRUCTURE IDENTIFICATION IN RELATIONAL DATA [J].

DECHTER, R ;

PEARL, J .

ARTIFICIAL INTELLIGENCE, 1992, 58 (1-3) :237-270

← 1 2 3 →