On the Complexity of Intersection Non-emptiness for Star-Free Language Classes: Logspace completeness at the first half-levelResearch Paper
Several specifications of a finite-state system may constrain the same sequence of events. Satisfying all of them requires a word accepted by every specification automaton. Intersection nonemptiness asks whether such a word exists. Its input is a list of finite automata, so the length of that list matters along with the sizes of the individual automata. The…