On uniformity within NC1

The study of circuit complexity classes within NC¹ in a uniform setting requires a uniformity condition that is more restrictive than those in common use. Two such conditions, stricter than NC¹ uniformity, have appeared in recent research. It is shown that the two notions are equivalent, leading to a natural notion of uniformity for low-level circuit complexity classes, and that recent results on the structure of NC¹ still hold true in this very uniform setting. A parallel notion of uniformity, still more restrictive, that is based on the regular languages is investigated. Characterizations of subclasses of the regular languages based on their logical expressibility are given