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?

  • 5
    $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.