Descriptional complexity of finite-state machines

点击翻译按钮获取中文摘要

My research on finite-state machines is part of the theory of computing. Algorithms based on finite-state machines are used in practically all areas of computing, from natural language processing to software verification. My work deals with lower bounds for the size of finite-state machines. This area of research is called descriptional complexity. When we have an implementation of a finite-state machine for a problem P, this gives an upper bound for the descriptional complexity of P. However, the crucial task is to establish lower bounds, that is, we have to prove that no machine of smaller size can solve the problem. Work on descriptional complexity contributes to our understanding of fundamental questions on the difficulty of computational problems. Descriptional complexity has recently become more important also from an applications point of view since finite-state machines used in natural language processing may require millions of states.