Current Answer Set Programming (ASP) solvers largely build on logic programming without function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e. g. , lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive such fragment that is useful, e. g. , for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and of some of their subclasses, addressing the main reasoning tasks. Our results also imply that the recently introduced FDNC programs can be extended by inverse predicates while retaining decidability, but computational costs are unavoidably higher.

Authors

• Thomas Eiter
• Mantas Simkus

Keywords

No keywords are indexed for this paper.