On decomposability and interaction functions

DOI10.3233/978-1-60750-606-5-9MaRDI QIDQ2999098zbMATH OpenFDO

Authors Knot Pipatsrisawat, Adnan Darwiche

Publication date 11 May 2011

Full work available at URL https://doi.org/10.3233/978-1-60750-606-5-9

Mathematics Subject Classification ID

Boolean functions (06E30) Data structures (68P05) Knowledge representation (68T30) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• The complexity of AND-decomposition of Boolean functions
• Positive and Horn decomposability of partially defined Boolean functions
• Decomposition of Boolean functions applying the apparatus of Boolean derivatives
• Algorithmic issues of AND-decomposition of Boolean formulas
• Decomposition of a system of incompletely specified Boolean functions defined with a binary decision diagram

Cited in

(7)

• The complexity of AND-decomposition of Boolean functions
• A polynomial Time Delta-Decomposition algorithm for positive DNFs
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• On the Decomposability of NC and AC
• On tractability of disjoint AND-decomposition of Boolean formulas
• Automatically finding the right probabilities in Bayesian networks
• Connecting knowledge compilation classes and width parameters

This page was built for publication: On decomposability and interaction functions

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