5 citations · 8 across the 5 of their papers we have counts for
5 papers
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…
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…
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…
Superlinear Lower Bounds Based on ETH
András Z. Salamon, Michael Wehar
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) i…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…