Uniform definability on finite structures with successor
Michel de Rougemont · 1984
We study inductive and second-order definability on finite structures with successor and relate these notions to complexity theory. We introduce the dimension d of an inductive definition, directly related to the Time complexity, representing the number of variables necessary to carry an induction. We will prove the following: