Skeptical reasoning in FC-Normal Logic Programs is P 11 complete

• Autorzy: Milnikel R.S.
• Języki publikacji: EN

Abstrakty

EN

FC-normal logic programs are a generalization by Marek, Nerode, and Remmel of Reiter's normal default theories. They have the property that, unlike most logic programs, they are guaranteed to have simple stable models. In this paper it is shown that the problem of skeptical reasoning in FC-normal programs is P11-complete, the same complexity as for logic programs without the restriction of FC-normality. FC-normal programs are defined in such a way as to make testing a program for FC-normality very difficult in general. A large subclass of FC-normal programs, locally FC-normal programs, is defined, shown to be recursive, and shown to have skeptical consequence as expressive as the entire class of FC-normal programs.

Słowa kluczowe

EN

FC-normal logic programs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 3
• Strony: 237--252
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Milnikel R.S.

• Department of Mathematics Wellesley College 106 Central St. Wellesley, MA 02481 USA