Descriptional complexity of finite-state machines

我对有限状态机的研究是计算理论的一部分。基于有限状态机的算法几乎应用于计算的所有领域，从自然语言处理到软件验证。我的工作涉及有限状态机大小的下限。这一研究领域被称为描述复杂性。当我们有一个问题P的有限状态机的实现时，这给出了P的描述复杂性的一个上界。然而，关键的任务是建立下界，即我们必须证明没有更小尺寸的机器可以解决这个问题。关于描述复杂性的工作有助于我们理解关于计算问题的困难的基本问题。从应用的角度来看，描述复杂性最近也变得更加重要，因为自然语言处理中使用的有限状态机可能需要数百万个状态。

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.