Efficient synthesis of a class of Boolean programs from II-OO data: Application to genetic networks

The paper addresses the problem of synthesizing programs using a restricted set of input–output data. The program to be synthesized consists of assigning, to individual Boolean variables x′x′, the result of evaluating functions involving other Boolean variables xx. The program can be initially viewed as a black box having nn inputs corresponding to the variables xx and nn outputs corresponding to the x′x′. The goal is to determine the Boolean functions that produce x′x′ given xx. It is shown that by suitably selecting a limited number of input sets to the black box and examining their output, the assignments can be fully reconstructed. The paper describes an effective representation of the Boolean functions, identifies related work, and provides an upper bound on the number of II-OO pairs needed to rebuild the program. The work is based on discrete Jacobians that are computed from the selected II-OO pairs. Finally, it is shown that the synthesis can be extended to programs whose variables are bounded integers. The results indicate that, if each Boolean function involves a small number of variables, a limited set of selectively chosen II-OO pairs suffices for synthesizing the program (instead of a potentially exponential number of pairs that would be needed in a worst case scenario). These results are of interest in the reverse engineering of genetic networks from biological experiments.