5 citations · 8 across the 5 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.CC2021
Effective Guessing Has Unlikely Consequences
András Z. Salamon, Michael Wehar
A classic result of Paul, Pippenger, Szemerédi and Trotter states that DTIME(n) is strictly contained in NTIME(n). The natural question then arises: could DTIME(t(n)) be contained…
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…