How complicated is the set of stable models of a recursive logic program? (Q1192346)

The notion of a stable model of a logic program was introduced by Gelfond and Lifschitz (1988). The present paper establishes that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has a stable model, is \(\Sigma^ 1_ 1\)-complete.