Portal de Periódicos da CAPES

Minimal Answer Computation and SOL

2002; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-45757-7_21

1611-3349

Koji Iwanuma, Katsumi Inoue,

Semantic Web and Ontologies

In this paper, we study minimal and/or conditional answer computing and its related problems. At first, we study some features of minimal answers, and show a non-finiteness property of minimal answers with no function symbols. Next, we show that SOL, which is a modelelimination- like calculus extended with Skip operation, is complete for computing not only correct answers, but also minimal answers. Unfortunately, SOL sometimes produces non-minimal answers. Thus, we next investigate another computational problem of minimal answers.We show undecidability theorems for several membership problems of the minimal answer set, which implies the impossibility of perfectly eliminating nonminimal answers. Finally, we address an extended computation problem, called conditional answer computing. SOL is also complete for computing minimal conditional answers.