2007): Model Checking the First-Order Fragment of Higher-Order Fixpoint Logic

Abstract. We present a model checking algorithm for HFL1, the first-order fragment of Higher-Order Fixpoint Logic. This logic is capable of expressing many interesting properties which are not regular and, hence, not expressible in the modal μ-calculus. The algorithm avoids best-case exponential behaviour by localising the computation of functions and can be implemented symbolically using BDDs. We show how insight into the behaviour of this procedure, when run on a fixed formula, can be used to obtain specialised algorithms for par-ticular problems. This yields, for example, the competitive antichain algorithm for NFA universality but also a new algorithm for a string matching problem.