Automatic Extraction of Functional Dependencies

In this paper, a new polynomial time technique for extracting functional dependencies in Boolean formulas is proposed. It makes an original use of the well-known Boolean constraint propagation technique (BCP) in a new preprocessing approach that extracts more hidden Boolean functions and dependent variables than previously published approaches on many classes of instances.

Authors

• Éric Grégoire
• Richard Ostrowski
• Bertrand Mazure
• Lakhdar Saïs

Keywords

• SAT
• Boolean function
• propositional reasoning and search