Nonmonotonic rule systems with recursive sets of restraints (Q1389245)

Nonmonotonic rule systems are introduced to capture the common features of several nonmonotonic logics as, e.g., auto-epistemic logic, default logic and general logic programs. A nonmonotonic rule system is a pair \((U,N)\) where \(U\) is a set and \(N\) is a collection of rules. Each rule \(r \in N \) consists of a set of premises (\( \subseteq U\)), a set of restraints (\(\subseteq U\)) and a conclusion \( c \in U\). If the set of restraints is empty, we have an ordinary monotonic (Tarskian) rule system. Otherwise, the system is called nonmonotonic and the restraints are used to control the application of the rules in the following sense: Given a set \(S \subseteq U\), a rule \(r\) can be applied if all its premises can be derived, but in addition, none of the restraints occur in \(S\). A derivation from an initial set \(I\) conforming to this principle is called an \(S\)-proof from \(I\). If \(S\) equals the set of \(S\)-provable elements, then \(S\) is called an extension of \((U,N)\). The paper concentrates on recursion-theoretic characterizations of the family \({\mathcal E}((U,N))\) of extensions of a nonmonotonic rule system \((U,N)\), especially for so-called extended recursive nonmonotonic rule systems, where the sets of restraints can be infinite, but recursive subsets of \(U\), and there is a uniform enumeration of codes for the rules \(r \in N\).