TITLE: Machine characterization of $SAC^i$
QUESTION [14 upvotes]: $SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It is known that $SAC^i$ for $i \geq 1$ is closed under complement and $SAC^0$ is not. Also, $SAC^1 = LogCFL$ and hence has a machine characterization, since LogCFL is the set of languages accepted by an $O({\log}n)$ space bounded and polynomial time bounded auxiliary PDA. Are there similar machine characterizations of $SAC^i$ for $i \geq 2$ ?

REPLY [14 votes]: Yes. Stack heights.  $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ bits.  We have 
$$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$$
these machines will run in time $2^{\log^{k}(n)}$.  Without restriction on stack height, we will get exactly $\mathsf{P}$.  The result should follow from: W. Ruzzo, Tree-size bounded alternation. JCSS 1980.
{"set_name": "stack_exchange", "score": 14, "question_id": 1590}