Efficient synthesis of a class of Boolean programs from I-O data: Application to genetic networks

摘要

The paper addresses the problem of synthesizing programs using a restricted set of inputoutput data. The program to be synthesized consists of assigning, to individual Boolean variables x′, the result of evaluating functions involving other Boolean variables x. The program can be initially viewed as a black box having n inputs corresponding to the variables x and n outputs corresponding to the x′. The goal is to determine the Boolean functions that produce x′ given x. 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 I-O pairs needed to rebuild the program. The work is based on discrete Jacobians that are computed from the selected I-O 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 I-O 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.