Istituto di Scienza e Tecnologie dell'Informazione     
Sebastiani F., Straccia U. A note on the complexity of 'simple' heterogeneous model-preference default theories. Internal note IEI-B4-37, 1990.
In a recent paper one of these authors argued that the notion of maximality (which he dubbed "≤-maximality") which Selman and Kautz's model-preference default systems rely upon leads to unintuitive results in the heterogeneous case; as a result, he proposed a new notion of "≤∆i-maximality" that fixes the problem. In this paper we show that in all model-preference default systems reasoning with ≤∆i-maximality in the simple heterogeneous case is no harder than reasoning with ≤-maximality in the homogeneous case. This allows to extend to the simple heterogeneous case results found by Selman and Kautz for the homogeneous case. We also argue that, in practice, reasoning in the simple heterogeneous case is faster than in the homogeneous case.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional