![](/sites/default/files/styles/workshop_banner_sm_1x/public/complexity_logo_final.png.jpg?itok=H_SevtP4)
Abstract
FInite automata (FA) are among the basic structures every first-year student in Computer Science gets to know. Somehow, the impression is that many decision problems concerning FA are easy to solve. However, there are quite a number of questions that are indeed computationally difficult. We show various examples how the (strong) exponential time hypothesis helps show the limits of exponential-time algorithms for these cases.