Automata with limited nondeterminism and applications of automata

有限状态机或有限自动机是一种抽象的计算模型，是研究计算中基本问题的基础。有限自动机有许多应用，例如编译器、文本搜索、自然语言处理、web服务和程序验证。通过研究抽象模型（如有限自动机）的基本性质，我们可以更深入地了解计算的复杂性，特别是描述复杂性。在描述复杂性中，我们关心的是如何简洁地指定某些对象，例如算法。这与计算复杂性不同，计算复杂性量化了算法所使用的资源，例如时间。有限自动机常用的描述复杂性度量是“状态复杂性”，它量化了识别给定语言的自动机的最小状态数。从应用的角度来看，描述复杂性的问题也变得更加重要，因为自然语言处理中使用的有限自动机通常需要数百万个状态。不确定性是并行计算的一种模型。该提案的工作涉及使用有限不确定性的有限自动机，我们希望通过允许额外的并行性来确定我们可以减少多少状态，反之亦然。关键的任务是建立下限，也就是说，我们必须证明状态较少的机器不能识别相同的语言。我们可以使用通信复杂度技术来证明具有有限不确定性的自动机大小的下界。申请资金将支持每年4名研究生和1名本科生的研究活动。

Finite-state machines, or finite automata, are an abstract model of computation and a basis for the study of fundamental questions in computing. There are many applications of finite automata, for example, compilers, text searching, natural language processing, web services and program verification. By studying foundational properties of abstract models, such as finite automata, we can gain deeper insights into the complexity of computation, in particular, descriptional complexity. In descriptional complexity we are concerned with how succinctly certain objects, such as algorithms, can be specified. This is different from computational complexity which quantifies the resources, for example time, used by an algorithm. A commonly used descriptional complexity measure for finite automata is "state complexity" which quantifies the minimal number of states of an automaton recognizing a given language. Questions of descriptional complexity have become more important also from an applications point of view since finite automata used in natural language processing typically require millions of states. Nondeterminism is a model of parallel computation. The work of the proposal deals with finite automata employing limited nondeterminism and we want to determine how much we can reduce the number of states by allowing additional parallelism, and vice versa. The crucial task is to establish lower bounds, that is, we have to prove that no machine with fewer states can recognize the same language. We can use techniques of communication complexity to prove lower bounds for the size of automata with limited nondeterminism.The requested funding will support the research activity of 4 graduate students and one undergraduate student each year.