Theory and Practice of Logic Programming

Regular Papers

A decidable subclass of finitary programs


a1 Università di Napoli “Federico II”, Italy


Answer set programming—the most popular problem solving paradigm based on logic programs—has been recently extended to support uninterpreted function symbols (Syrjänen 2001, Bonatti 2004; Simkus and Eiter 2007; Gebser et al. 2007; Baselice et al. 2009; Calimeri et al. 2008). All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 is inspired by the extension of finitary normal programs with local variables introduced in (Bonatti 2004, Section 5). FP2 programs enjoy the following unique combination of properties: (i) the ability of expressing predicates with infinite extensions; (ii) full support for predicates with arbitrary arity; (iii) decidability of FP2 membership checking; (iv) decidability of skeptical and credulous stable model reasoning for call-safe queries. Odd cycles are supported by composing FP2 programs with argument restricted programs.

(Received February 07 2010)

(Revised April 29 2010)

(Accepted May 14 2010)


  • answer set programming with function symbols;
  • infinite stable models;
  • norms