A Hierarchy of Tractable Subsets for Computing Stable Models
| dc.creator | Ben-Eliyahu, R. | |
| dc.date | 1996-08-01 | |
| dc.date.accessioned | 2026-07-07T09:12:20Z | |
| dc.date.available | 2026-07-07T09:12:20Z | |
| dc.description | Finding the stable models of a knowledge base is a significant computational problem in artificial intelligence. This task is at the computational heart of truth maintenance systems, autoepistemic logic, and default logic. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Omega_1,Omega_2,..., with the following properties: first, Omega_1 is the class of all stratified knowledge bases; second, if a knowledge base Pi is in Omega_k, then Pi has at most k stable models, and all of them may be found in time O(lnk), where l is the length of the knowledge base and n the number of atoms in Pi; third, for an arbitrary knowledge base Pi, we can find the minimum k such that Pi belongs to Omega_k in time polynomial in the size of Pi; and, last, where K is the class of all knowledge bases, it is the case that union{i=1 to infty} Omega_i = K, that is, every knowledge base belongs to some class in the hierarchy. | |
| dc.description | See http://www.jair.org/ for any accompanying files | |
| dc.identifier | https://arxiv.org/abs/cs/9608104 | |
| dc.identifier | http://arxiv.org/abs/cs/9608104 | |
| dc.identifier | Journal of Artificial Intelligence Research, Vol 5, (1996), 27-52 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151987 | |
| dc.subject | Artificial Intelligence | |
| dc.title | A Hierarchy of Tractable Subsets for Computing Stable Models | |
| dc.type | text |