Abstract
The stable model semantics was recently generalized by Ferraris, Lee and Lifschitz to the full first-order language with a syntax translation approach that is very similar to McCarthy's circumscription. In this paper, we investigate the decidability and undecidability of various fragments of first-order language under both semantics of stable models and circumscription. Some maximally decidable classes and undecidable classes are identified. The results obtained in the paper show that the boundaries between decidability and undecidability for these two semantics are very different in spite of the similarity of definition. Moreover, for all fragments considered in the paper, decidability under the semantics of circumscription coincides with that in classical first-order logic. This seems rather counterintuitive due to the second-order definition of circumscription and the high undecidability of first-order circumscription.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-fourth AAAI Conference on Artificial Intelligence (AAAI-10), 11-15 July 2010, Atlanta, Georgia, USA |
| Publisher | AAAI Press |
| Pages | 375-380 |
| Number of pages | 6 |
| ISBN (Print) | 9781577354635 |
| Publication status | Published - 2010 |
| Event | AAAI Conference on Artificial Intelligence - Duration: 22 Jul 2012 → … |
Conference
| Conference | AAAI Conference on Artificial Intelligence |
|---|---|
| Period | 22/07/12 → … |