Analyzing the Structure of Definitions in ID-logic ∗

ID-logic uses ideas from logic programming to extend classical logic with non-monotone inductive definitions. Here, we study the structure of definitions expressed in this formalism. We define the fundamental concept of a dependency relation, both in an abstract, algebraic context and in the concrete setting of ID-logic. We also characterize dependency relations in a more constructive way. Our results are used to study the relation between ID-logic and known classes of inductive definitions and to show the correctness of ID-logic semantics in these cases