What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}?

If we believe Theorem 2 in

Koucký, Circuit Complexity of Regular Languages, LNCS 4497, 2007,

then it's NC¹. Is the author right? Are tighter upper bounds on REG known in the meantime?

  • 6
    $\begingroup$ There exist NC^1-complete regular languages, so you are not going to get better bounds. See also cstheory.stackexchange.com/questions/33487/regular-versus-tc0 . $\endgroup$ Commented Feb 1, 2018 at 12:43
  • 1
    $\begingroup$ Isn't all of REG in NC^1 by just divide and conquer on a run of the automaton? $\endgroup$
    – Nikhil
    Commented Feb 1, 2018 at 13:20
  • $\begingroup$ @Nikhil I'm afraid I don't get you here. What does a "divide and conquer on a run of the automaton" look? $\endgroup$
    – user48424
    Commented Feb 1, 2018 at 16:09
  • 3
    $\begingroup$ @Leon Meier an automaton has constantly many states. Draw a DAG of width q (where q is the number of states in the automaton) and length n (which is the length of the word for which you want to test acceptance) and put edges according to the transition function. This is essentially a bounded width branching program and you can use a Savitch kinda divide and conquer for reachability on this graph to get an NC^1 circuit. $\endgroup$
    – Nikhil
    Commented Feb 1, 2018 at 16:26
  • 3
    $\begingroup$ @LeonMeier: I believe you'd be interested in reading Straubing's 1994 book on automata, circuits, and logic. In the meantime, I don't believe this is a research-level question. $\endgroup$ Commented Feb 2, 2018 at 10:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.