STATIONARY DEFAULT EXTENSIONS
Halina Przymusinska, Teodor C. Przymusiński · Fundamenta Informaticae · 1994
this paper we introduce the class of so called stationary extensions of a default theory. Stationary extensions include, as a special case, Reiter's original default extensions but allow us to eliminate their drawbacks that were mentioned above. Every default theory \\Delta has at least one stationary extension and among its extensions there always exists the least stationary extension E \\Delta . The (cautious) stationary semantics S (\\Delta) of a default theory \\Delta, i.e., the theory consisting of sentences which are true in all stationary extensions of \\Delta, is always well-defined, and, since it clearly coincides with the least stationary extension E \\Delta of \\Delta, it is itself a stationary extension of \\Delta. The stationary semantics of default theories is always cumulatively monotonic and it can be computed by means of a natural iterative procedure. The complexity of its computation essentially coincides with the computational complexity of satisfiability tests on the underlying first order theory and therefore it does not involve any additional complexity caused by the non-monotonicity of default logic. More precisely, for default theories consisting of