2 citations · 2 across the 1 of their papers we have counts for
Showing cs.FLShow all
2 papers · 1 filter
cs.FL2025
Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
Michael Wehar
We reinvestigate known lower bounds for the Intersection Non-Emptiness Problem for Deterministic Finite Automata (DFA's). We first strengthen conditional time complexity lower boun…
cs.FL2021★ 2 cited
Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited
Henning Fernau, Stefan Hoffmann, Michael Wehar
The problem DFA-Intersection-Nonemptiness asks if a given number of deterministic automata accept a common word. In general, this problem is PSPACE-complete. Here, we investigate t…