What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)
Professor Immerman kindly answered this by email:


  The definition of FO(REGULAR) is the set of all decision problems that are reducible to some regular language via first-order reductions.


Additionally, since the word problem for $S_5$ (which is a regular language) is complete for $\mathsf{NC}^1$ under FO reductions, this means that FO(REGULAR) can be defined equivalently as the set of decision problems that are reducible to $S_5$.



Other logics equivalent to $\mathsf{NC}^1$:


FO with monoidal quantifiers (Barrington, Immerman, Straubing, 1990: On uniformity within NC1)
FO with "relational primitive recursion" and the BIT relation (Compton, Laflamme, 1990: An algebra and a logic for NC1)
FO with width-5 transitive closure (Immerman, 1987: Expressibility as a Complexity Measure: Results and Directions)