%0 Journal Article %1 EiterIJCAI2009Bidirectional %A Simkus, M. %A Eiter, T. %D 2009 %E Boutilier, C. %J Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press/IJCAI, 2009. %K artificial function ontorule %P 765-771 %T Bidirectional answer set programs with function symbols %U http://ijcai.org/papers09/Papers/IJCAI09-132.pdf %X 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 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.

@article{EiterIJCAI2009Bidirectional, abstract = {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 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.}, added-at = {2010-03-29T16:22:00.000+0200}, author = {Simkus, M. and Eiter, T.}, biburl = {https://www.bibsonomy.org/bibtex/2de0b84634d9778b9170321d8463e22fe/ontorule}, editor = {Boutilier, C.}, interhash = {698c1d67bf5af9adcff316b8252096aa}, intrahash = {de0b84634d9778b9170321d8463e22fe}, journal = {Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press/IJCAI, 2009.}, keywords = {artificial function ontorule}, month = {July}, pages = {765-771}, timestamp = {2010-03-29T16:22:00.000+0200}, title = {Bidirectional answer set programs with function symbols}, url = {http://ijcai.org/papers09/Papers/IJCAI09-132.pdf}, year = 2009 }