Function Symbols in ASP: Overview and Perspectives

Answer Set Programming (ASP) is a highly expressive language that is widely used for knowledge representation and reasoning in many application scenarios. Thanks to disjunction and negation, the language allows the use of nondeterministic definitions for modeling complex problems in computer science, in particular in Artificial Intelligence. Traditionally, ASP has often been used as a first-order language without function symbols, similar to Datalog, in order to deal with finite structures only. More recently, also uninterpreted function symbols have been frequently considered in the setting of ASP, enabling a natural representation of recursive structures. Function symbols can be used for encoding strings, lists, stacks, trees and many other common data structures. However, the common reasoning tasks are undecidable for programs with no restrictions on the usage of function symbols. Therefore, identifying relevant classes of programs with decidable reasoning is important for practical applications, and many authors have addressed this issue in the past decade. This article provides a survey of the decidability results for ASP programs with functions.We classify the decidable ASP programs in three main groups: programs allowing for finite bottom-up evaluations; programs suitable for finite top-down evaluations; programs characterized by finite representations of stable models. We focus on the decidability of ground reasoning and computability of non-ground reasoning. Moreover, we consider decidability of coherence checking and of class membership; expressiveness issues are briefly discussed as well.