On the complexity of inductive definitions
Douglas Cenzer, Jeffrey B. Remmel · Mathematical Structures in Computer Science · 2006
We study the complexity of computable and -definitions that are computable. We also examine the complexity of a new type of inductive definition, which we call weakly finitary monotone inductive definitions. Applications are given in proof theory and in logic programming.