A note on the complexity of 'simple' heterogeneous model-preference default theories

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.