Gap Theorems for the Delay of Circuits Simulating Finite Automata

Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger

We study the delay (also known as depth) of circuits that simulate finite automata, showing that only certain growth rates (as a function of the number $n$ of steps simulated) are…