The problem of Interactive Boolean Evaluation [1]}, [2]}, [3]} and BDD optimization has been extensively studied in multiple contexts. These include system testing, e.g., [2]}, [5]}
(where it is called Sequential System Testing or Sequential Diagnosis), BDD design, e.g., [6]}, [7]}, [8]} (where it is also called Discrete Function Evaluation), active learning [9]} (where it is a particular case of Bayesian Active Learning) and its connection to other problems such as Stochastic Set Cover [3]}, [11]}
(where it is termed Stochastic Boolean Function Evaluation (SBFE)). Boolean Evaluation is also a component of Consent Management [12]}, [13]}, where the choice of variables to observe coincides with requests to attain consent to use specific input tuples.
Many of these studies focus on optimization goals different than ours, most notably the expected number of observed variables under a probabilistic model [1]}, [12]}, [2]}, [6]}, [3]}, [13]}, [11]}, [8]}, [5]}, corresponding to the expected path length in a BDD; but other alternatives such as minimizing the size of the BDD have been considered [23]}.
