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$ – Emil Jeřábek Feb 1 '18 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 Feb 1 '18 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 Feb 1 '18 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 Feb 1 '18 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$ – Michaël Cadilhac Feb 2 '18 at 10:45

Your Answer

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