2

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
    There exist NC^1-complete regular languages, so you are not going to get better bounds. See also https://cstheory.stackexchange.com/questions/33487/regular-versus-tc0 . – Emil Jeřábek Feb 01 '18 at 12:43
  • 1
    Isn't all of REG in NC^1 by just divide and conquer on a run of the automaton? – Nikhil Feb 01 '18 at 13:20
  • @Nikhil I'm afraid I don't get you here. What does a "divide and conquer on a run of the automaton" look? –  Feb 01 '18 at 16:09
  • 3
    @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. – Nikhil Feb 01 '18 at 16:26
  • 3
    @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. – Michaël Cadilhac Feb 02 '18 at 10:45
  • @EmilJeřábek reply is perfect, the question should be closed. – C.P. Jul 19 '18 at 09:52

0 Answers0