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.