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.