Grounding for model expansion in k-guarded formulas with inductive definitions

Mitchell and Ternovska [LCC'05, AAAI'05] propose a constraint programming framework for search problems that is based on classical logic extended with inductive definitions. They formulate a search problem as the problem of model expansion (MX). In this framework, the problem is encoded in a logic, an instance of the problem is represented by a finite structure, and a solver generates solutions to the problem. This approach relies on propositionalisation of high-level specifications, and on the efficiency of modern SAT solvers. Here, we propose an efficient algorithm which combines grounding with partial evaluation. Since the MX framework is based on classical logic, we are able to take advantage of known results for the so-called guarded fragments and their generalizations. In the case of k-guarded formulas with inductive definitions under a natural restriction, the algorithm performs much better than naive grounding by relying on connections between k-guarded formulas and tree decompositions.