Structure-Aware Computing By Partial Quantifier Elimination
<|reference_start|>Structure-Aware Computing By Partial Quantifier Elimination: By structure-aware computing (SAC) we mean computing that is formula-specific i.e., takes into account the structure of the formula at hand. Virtually all efficient algorithms of hardware verification employ some form of SAC. We relate SAC to $\mathit{partial}$ $\mathit{quantifier}$ $\mathit{elimination}$ (PQE). The latter is a generalization of regular quantifier elimination where one can take a $\mathit{part}$ of the formula out of the scope of quantifiers. The objective of this paper is to emphasize the significance of studying PQE for enhancing the $\mathit{existing}$ methods of SAC and creating $\mathit{new}$ ones. First, we show that interpolation (that can be viewed as an instance of SAC) is a special case of PQE. Then we describe application of SAC by PQE to three different problems of hardware verification: property generation, equivalence checking and model checking. Besides, we discuss using SAC by PQE for SAT solving.<|reference_end|>
@article{goldberg2024structure-aware,
    title={Structure-Aware Computing By Partial Quantifier Elimination},
    author={Eugene Goldberg},
    journal={arXiv preprint arXiv:2403.05928},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05928},
    primaryClass={cs.LO}
}