A characterization of alternating log time by ramified recurrence
Résumé
We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the $U_{E^*}$-uniform variant of ${\rm NC}^1$ \cite{Ruzzo81}. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.