Summary: In answer set programming (ASP) systems, the computation consists of two main phases: (1) the input program is first instantiated and simplified, generating a ground (i.e., variable free) program, (2) propositional algorithms are then applied on the ground program to generate the answer sets. The instantiation process may be computationally expensive and the instantiator is crucial for the efficiency of the entire ASP system, especially in real-world applications. In this paper, we propose to employ main-memory indexing techniques for enhancing the performance of the instantiation procedure of the ASP system DLV. In particular, we adapt a classical first argument indexing schema to our context, and propose an on demand indexing strategy where indexes are computed during the evaluation (and only if exploitable). Moreover, we define two heuristics which can be used for determining the most appropriate argument to be indexed, when more than one possibility exists. We have implemented such techniques in the DLV instantiator, and we have carried out an experimentation activity on a collection of benchmark problems, including also a number of real-world instances. The results of experiments are very positive and confirm the intuition that indexing allows for notably improving the efficiency of the instantiation process. Moreover, the on demand indexing strategy always outperforms the classical first argument schema, especially when the argument to be indexed is chosen according to a better heuristic.
For the entire collection see [Zbl 1217.68007].