Checking membership in DFA with fixed length using AC1 circuit?

Question

I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should be the way to go, but I always exceed the max size. Would really appreciate any help

Answer 1

Let $T$ by a balanced binary tree with $n$ leaves, and label each internal node $v$ by the interval $I_v$ consisting of the leaves below $v$. For each $v$ we will calculate the a two-place relation $R_v(s,t)$ which checks whether $I_v$ causes the automaton to move from $s$ to $t$. If $a,b$ are the two children of $v$, then $$ R_v(s,t) = \bigvee_u (R_a(s,u) \land R_b(u,t)). $$ For a leaf $f$, $R_f(s,t) = [\delta(s,x_f) = t]$, where $x_f$ is the $f$th input, and $\delta$ is the transition function. If $r$ is the root of the tree then the final answer is $$ \bigvee_{q \in F} R_r(q_0,q), $$ where $q_0$ is the initial state and $F$ is the set of accepting states.

Each node of the tree uses $O(1)$ gates. Since the tree has $O(n)$ nodes, the circuit has size $O(n)$. It's also not difficult to check that it has depth $O(\log n)$. Moreover, the fan-in of each gate is constant (since the number of states is constant), and so this circuit is actually in $\mathsf{NC}^1$.

Note also that the construction works directly for NFAs.