Polynomially bounded logic programs with function symbols : a new decidable class

Vernon Asuncion; Yan Zhang; Heng Zhang

Polynomially bounded logic programs with function symbols : a new decidable class

Western Sydney University

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

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 EXPTIME-complete.

Original language	English
Title of host publication	Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17): 4-10 February 2017, San Francisco, California, USA
Publisher	AAAI Press
Pages	1041-1047
Number of pages	7
Publication status	Published - 2017
Event	AAAI Conference on Artificial Intelligence - , United States Duration: 1 Jan 1980 → …

Conference

Conference	AAAI Conference on Artificial Intelligence
Country/Territory	United States
Period	1/01/80 → …

Keywords

artificial intelligence
computational complexity
logic programming

Cite this

@inproceedings{3601632e7b2c4a5c9b1a1e9222d4d022,

title = "Polynomially bounded logic programs with function symbols : a new decidable class",

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 EXPTIME-complete.",

keywords = "artificial intelligence, computational complexity, logic programming",

author = "Vernon Asuncion and Yan Zhang and Heng Zhang",

year = "2017",

language = "English",

pages = "1041--1047",

booktitle = "Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17): 4-10 February 2017, San Francisco, California, USA",

publisher = "AAAI Press",

note = "AAAI Conference on Artificial Intelligence ; Conference date: 01-01-1980",

}

Polynomially bounded logic programs with function symbols : a new decidable class. / Asuncion, Vernon ; Zhang, Yan; Zhang, Heng.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17): 4-10 February 2017, San Francisco, California, USA. AAAI Press, 2017. p. 1041-1047.

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

TY - GEN

T1 - Polynomially bounded logic programs with function symbols : a new decidable class

AU - Asuncion, Vernon

AU - Zhang, Yan

AU - Zhang, Heng

PY - 2017

Y1 - 2017

N2 - 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 EXPTIME-complete.

AB - 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 EXPTIME-complete.

KW - artificial intelligence

KW - computational complexity

KW - logic programming

UR - http://handle.westernsydney.edu.au:8081/1959.7/uws:44495

UR - https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14163

M3 - Conference Paper

SP - 1041

EP - 1047

BT - Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17): 4-10 February 2017, San Francisco, California, USA

PB - AAAI Press

T2 - AAAI Conference on Artificial Intelligence

Y2 - 1 January 1980

ER -

Polynomially bounded logic programs with function symbols : a new decidable class

Abstract

Conference

Keywords

Other files and links

Fingerprint

Cite this