Finite Groundings for ASP with Functions: A Journey through Consistency (Technical Report)

Lukas GerlachLukas Gerlach, David CarralDavid Carral, Markus HecherMarkus Hecher

Lukas Gerlach, David Carral, Markus Hecher
Finite Groundings for ASP with Functions: A Journey through Consistency (Technical Report)
In Kate Larson, eds., Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, 3386-3394, August 2024. International Joint Conferences on Artificial Intelligence Organization

Details
Bibtex

KurzfassungAbstract
Answer set programming (ASP) is a logic programming formalism used in various areas of artificial intelligence like combinatorial problem solving and knowledge representation and reasoning. It is known that enhancing ASP with function symbols makes basic reasoning problems highly undecidable. However, even in simple cases, state of the art reasoners, specifically those relying on a ground-and-solve approach, fail to produce a result. Therefore, we reconsider consistency as a basic reasoning problem for ASP. We show reductions that give an intuition for the high level of undecidability. These insights allow for a more fine-grained analysis where we characterize ASP programs as "frugal" and "non-proliferous". For such programs, we are not only able to semi-decide consistency but we also propose a grounding procedure that yields finite groundings on more ASP programs with the concept of "forbidden" facts.
Projekt:Project: Cfaed, CPEC, SECAI, ScaDS.AI
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{GCH2024,
  author    = {Lukas Gerlach and David Carral and Markus Hecher},
  title     = {Finite Groundings for {ASP} with Functions: A Journey through
               Consistency (Technical Report)},
  editor    = {Kate Larson},
  booktitle = {Proceedings of the Thirty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-24}},
  publisher = {International Joint Conferences on Artificial Intelligence
               Organization},
  year      = {2024},
  month     = {August},
  pages     = {3386-3394},
  doi       = {10.24963/ijcai.2024/375}
}