Decomposability of partially defined Boolean functions

DOI10.1016/0166-218X(94)00145-4MaRDI QIDQ1900137zbMATH OpenDBLPWikidataFDO

Authors Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Alex Kogan, Vladimir Gurvich

Publication date 11 March 1996

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

Full work available at URL https://doi.org/10.1016/0166-218X(94)00145-4

zbMATH Keywords

decomposabilityNP-completenesspartially defined Boolean functionspartially functions

Mathematics Subject Classification ID

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

Recommendations

• Positive and Horn decomposability of partially defined Boolean functions
• A decomposition of Boolean functions
• scientific article; zbMATH DE number 1931923
• On irreduceability of Boolean functions with respect to commutative associative operation

Cites work

• scientific article; zbMATH DE number 4164874 (Why is no real title available?)
• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 49085 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3319969 (Why is no real title available?)
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• scientific article; zbMATH DE number 3422228 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Complex Disjunctive Decomposition of Incompletely Specified Boolean Functions
• Compositional complexity of Boolean functions
• Decomposing a relation into a tree of binary relations
• Decompositions of positive self-dual Boolean functions
• Structure identification in relational data
• Synthesis of Combinational Logic Using Decomposition and Probability

Cited in

(24)

• scientific article; zbMATH DE number 1436990 (Why is no real title available?)
• Separable discrete functions: recognition and sufficient conditions
• Bidual Horn functions and extensions
• scientific article; zbMATH DE number 5924797 (Why is no real title available?)
• scientific article; zbMATH DE number 6155508 (Why is no real title available?)
• A decomposition of Boolean functions
• Logical analysis of data -- the vision of Peter L. Hammer
• Mining determining sets for partially defined functions using entropy
• scientific article; zbMATH DE number 597624 (Why is no real title available?)
• On a convex geometric connection to threshold logic
• scientific article; zbMATH DE number 5174795 (Why is no real title available?)
• Logical analysis of data: classification with justification
• Properties of quasi-Boolean function on quasi-Boolean algebra
• scientific article; zbMATH DE number 3989366 (Why is no real title available?)
• Logical analysis of numerical data
• On irreduceability of Boolean functions with respect to commutative associative operation
• Logical analysis of binary data with missing bits
• The complexity of modular decomposition of Boolean functions
• Decomposition of a system of incompletely specified Boolean functions defined with a binary decision diagram
• Inner-core and outer-core functions of partially defined Boolean functions
• Pareto-optimal patterns in logical analysis of data
• Error-free and best-fit extensions of partially defined Boolean functions
• Logical analysis of data with decomposable structures.
• A decomposability index in logical analysis of data

This page was built for publication: Decomposability of partially defined Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900137)