Logic programming and autoepistemic logics: New relations and complexity results

In recent years, many authors have pointed out the strict correlation between non-Horn logic programs and non-monotonic reasoning. As a result, many studies on the relations between various semantics for negation and non-monotonic logics have appeared in the literature. The analysis of these relations helps understanding the properties of the various systems and allows importing analysis from one formalism into another one. In this paper we show a one-to-one mapping between the positivistic models and moderately-grounded expansions of autoepistemic logic and a one-to-one correspondence between the minimally-supported models and the stable parsimonious expansions. These relations are then used to prove the computational complexity of reasoning with the positivistic and minimally-supported model semantics, as well as new complexity results for restricted subsets of autoepistemic logic.