Predicate Abstraction with Indexed Predicates
<|reference_start|>Predicate Abstraction with Indexed Predicates: Predicate abstraction provides a powerful tool for verifying properties of infinite-state systems using a combination of a decision procedure for a subset of first-order logic and symbolic methods originally developed for finite-state model checking. We consider models containing first-order state variables, where the system state includes mutable functions and predicates. Such a model can describe systems containing arbitrarily large memories, buffers, and arrays of identical processes. We describe a form of predicate abstraction that constructs a formula over a set of universally quantified variables to describe invariant properties of the first-order state variables. We provide a formal justification of the soundness of our approach and describe how it has been used to verify several hardware and software designs, including a directory-based cache coherence protocol.<|reference_end|>
@article{lahiri2004predicate,
    title={Predicate Abstraction with Indexed Predicates},
    author={Shuvendu K. Lahiri, Randal E. Bryant},
    journal={arXiv preprint arXiv:cs/0407006},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0407006},
    primaryClass={cs.LO}
}