Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols

Greco, Sergio; Molinaro, Cristian; Trubitsyna, Irina

Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols

Sergio Greco, Cristian Molinaro, Irina Trubitsyna

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 926-930.

Abstract

While function symbols are widely acknowledged as an important feature in logic programming, they make common inference tasks undecidable. To cope with this problem, recent research has focused on identifying classes of logic programs imposing restrictions on the use of function symbols, but guaranteeing decidability of common inference tasks. This has led to several criteria, called termination criteria, providing sufficient conditions for a program to have finitely many stable models, each of finite size.This paper introduces the new class of bounded programs which guarantees the aforementioned property and strictly includes the classes of programs determined by current termination criteria. Different results on the correctness, the expressiveness, and the complexity of the class of bounded programs are presented.

Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. 2013. Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 926–930. https://ijcai.org/proceedings/2013/142

@inproceedings{ijcai2013p142,
  title     = {Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols},
  author    = {Greco, Sergio and Molinaro, Cristian and Trubitsyna, Irina},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {926--930},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/142},
}

TY  - CPAPER
TI  - Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols
AU  - Greco, Sergio
AU  - Molinaro, Cristian
AU  - Trubitsyna, Irina
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 926
EP  - 930
UR  - https://ijcai.org/proceedings/2013/142
ER  -