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.