Decomposability of partially defined Boolean functions

DOI10.1016/0166-218X(94)00145-4zbMath0833.68090WikidataQ59560933 ScholiaQ59560933MaRDI QIDQ1900137

Toshihide Ibaraki, Peter L. Hammer, Endre Boros, Alexander Kogan, Vladimir A. Gurvich

Publication date: 11 March 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenessdecomposabilitypartially defined Boolean functionspartially functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)

Related Items

A decomposability index in logical analysis of data, Pareto-optimal patterns in logical analysis of data, Logical analysis of data -- the vision of Peter L. Hammer, The complexity of modular decomposition of Boolean functions, Logical analysis of numerical data, Error-free and best-fit extensions of partially defined Boolean functions, Properties of quasi-Boolean function on quasi-Boolean algebra, Logical analysis of data: classification with justification, Bidual Horn functions and extensions, Inner-core and outer-core functions of partially defined Boolean functions, Separable discrete functions: recognition and sufficient conditions, Logical analysis of data with decomposable structures., Logical analysis of binary data with missing bits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposing a relation into a tree of binary relations
• Compositional complexity of Boolean functions
• Structure identification in relational data
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Decompositions of positive self-dual Boolean functions
• Synthesis of Combinational Logic Using Decomposition and Probability
• Complex Disjunctive Decomposition of Incompletely Specified Boolean Functions