Polynomially Bounded Logic Programs with Function Symbols: A New Decidable
Abstract
A logic program with function symbols is called finitely ground if there is a finite propositional logic program whose stable models are exactly the same as the stable models of this program. Finite groundability is an important property for logic programs with function symbols because it makes feasible to compute such program’s stable models using traditional ASP solvers. In this paper, we introduce a new decidable class of finitely ground programs called POLY-bounded programs, which, to the best of our knowledge, strictly contains all decidable classes of finitely ground programs discovered so far in the literature. We also study the related complexity property for this class of programs. We prove that deciding whether a program is POLY-bounded is EXPTIMEcomplete.
Cite
Text
Asuncion et al. "Polynomially Bounded Logic Programs with Function Symbols: A New Decidable." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10669Markdown
[Asuncion et al. "Polynomially Bounded Logic Programs with Function Symbols: A New Decidable." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/asuncion2017aaai-polynomially/) doi:10.1609/AAAI.V31I1.10669BibTeX
@inproceedings{asuncion2017aaai-polynomially,
title = {{Polynomially Bounded Logic Programs with Function Symbols: A New Decidable}},
author = {Asuncion, Vernon and Zhang, Yan and Zhang, Heng},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2017},
pages = {1041-1047},
doi = {10.1609/AAAI.V31I1.10669},
url = {https://mlanthology.org/aaai/2017/asuncion2017aaai-polynomially/}
}