Positive and Horn decomposability of partially defined Boolean functions

DOI10.1016/S0166-218X(96)00053-4zbMath0873.06011OpenAlexW2090464622MaRDI QIDQ1356507

Kojin Yano, Kazuhisa Makino, Toshihide Ibaraki

Publication date: 29 October 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

complexitydecompositionNP-completepositive functionsdecomposabilityHorn functionsnegative examplespartial Boolean functionspositive examples

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30)

Related Items

A decomposability index in logical analysis of data, Bidual Horn functions and extensions, 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
• Structure identification in relational data
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Error-free and best-fit extensions of partially defined Boolean functions
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Synthesis of Combinational Logic Using Decomposition and Probability
• Horn Extensions of a Partially Defined Boolean Function
• Complex Disjunctive Decomposition of Incompletely Specified Boolean Functions