On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection

We study the fine grained complexity of the DFA non-emptiness of intersection problem parameterized by the number k of input automata (k -DFA-NEI). More specifically, we are given a list [Formula: see text] of DFA’s over a common alphabet [Formula: see text], and the goal is to determine whether [Formula: see text]. This problem can be solved in time [Formula: see text] by applying the classic Rabin-Scott product construction. In this work, we show that the existence of algorithms solving k -DFA-NEI in time slightly faster than [Formula: see text] would imply the existence of deterministic sub-exponential time algorithms for the simulation of nondeterministic linear space bounded computations. This consequence strengthens the existing conditional lower bounds for k-DFA-NEI and implies new non-uniform circuit lower bounds.