Dynamic Programming for Symbolic Boolean Realizability and Synthesis
<|reference_start|>Dynamic Programming for Symbolic Boolean Realizability and Synthesis: Inspired by recent progress in dynamic programming approaches for weighted model counting, we investigate a dynamic-programming approach in the context of boolean realizability and synthesis, which takes a conjunctive-normal-form boolean formula over input and output variables, and aims at synthesizing witness functions for the output variables in terms of the inputs. We show how graded project-join trees, obtained via tree decomposition, can be used to compute a BDD representing the realizability set for the input formulas in a bottom-up order. We then show how the intermediate BDDs generated during realizability checking phase can be applied to synthesizing the witness functions in a top-down manner. An experimental evaluation of a solver -- DPSynth -- based on these ideas demonstrates that our approach for Boolean realizabilty and synthesis has superior time and space performance over a heuristics-based approach using same symbolic representations. We discuss the advantage on scalability of the new approach, and also investigate our findings on the performance of the DP framework.<|reference_end|>
@article{lin2024dynamic,
    title={Dynamic Programming for Symbolic Boolean Realizability and Synthesis},
    author={Yi Lin, Lucas M. Tabajara, and Moshe Y. Vardi},
    journal={arXiv preprint arXiv:2405.07975},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07975},
    primaryClass={cs.FL cs.LO}
}