Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.

To prove the theorem stated above we need some theorems and definitions given below :

Barrington Theorem : A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in $\mathsf{\text{}NC^1}$.

Proof Idea of Barrington Theorem is like small depth boolean circuit implies small group program and small group program implies small branching program.

Monoid : In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I google and find out a research paper but not able to understand much (some of the things that I have understood I have written above). A high level proof idea or an resource to prove the theorem stated above will be helpful.


Let $L$ be a regular language. Take some DFA $\langle q_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $q \mapsto \delta(q,\sigma)$. In other words, if $Q = \{q_1,\ldots,q_m\}$, then in input $\sigma$, the circuit computes the sequence $\delta(q_1,\sigma), \ldots, \delta(q_m,\sigma)$.

There is another constant size circuit whose inputs are two functions $f,g\colon Q \to Q$ (such as the outputs of the circuit above), and whose output is their composition $q \mapsto f(g(q))$. As before, we encode the inputs and outputs as sequences of $m$ states.

Given $n$, construct a circuit that computes whether a given input word $\sigma_1 \ldots \sigma_n$ belongs to $L$ as follows. Assume by simplicity that $n = 2^t$.

  • Compute the functions $q \mapsto \delta(q,\sigma_1), \ldots, q \mapsto \delta(q,\sigma_n)$ using the constant size circuit from the first paragraph.
  • Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2), \ldots, q \mapsto \delta(q,\sigma_{n-1}\sigma_n)$ using the constant size composition circuit from the second paragraph.
  • Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2\sigma_3\sigma_4), \ldots, q \mapsto \delta(q,\sigma_{n-3} \sigma_{n-2} \sigma_{n-1} \sigma_n)$ using the constant size composition circuit.
  • Continue in the same way for $t-2$ more levels, until you compute the function $\varphi$ given by $q \mapsto \delta(q, \sigma_1\ldots\sigma_n)$.
  • Using a constant size circuit, determine whether $\varphi(q_0) \in F$.

This circuit has depth $O(\log n)$ and size $O(n)$, and moreover it is uniform in $n$. This shows that $L \in \mathsf{NC^1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.