Strong equivalence for causal theories

Strong equivalence is an important property for nonmonotonic formalisms, allowing safe local changes to a nonmonotonic theory This paper considers strong equivalence for nonmonotonic causal theories of the kind introduced by McCain and Turner. Causal theories T1 and T2 are strongly equivalent if, for every causal theory T, T1 U T and T2 U T are equivalent (that is, have the same causal models). The paper introduces a convenient characterization of this property in terms of so-called SE-models, much as was done previously for answer set programs and default theories. A similar result is provided for the nonmonotonic modal logic UCL. The paper also introduces a reduction from the problem of deciding strong equivalence of two causal theories to the problem of deciding equivalence of two sets of propositional formulas.