New answers tagged

9 votes
Accepted

Is DFA language inclusion decidable in quasi-linear time?

EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis. https://cstheory.stackexchange.com/a/29166/2367 ORIGINAL ...
Hermann Gruber's user avatar

Top 50 recent answers are included