Complexity of Recursive Normal Default Logic

摘要: Normal default logic, the fragment of logic obtained by restricting defaults to rules form α:Mβ/β, is most important and widely studied part logic. In [20], we proved a basis theorem for extensions recursive propositional normal theories hence finite predicate theories. That is, that every theory possesses an extension which r.e. in 0′. Here show this bound tight. Specifically, set A B there 〈D, W〉 with unique Turing-equivalent t B. similar result holds