Automata with limited nondeterminism and applications of automata

点击翻译按钮获取中文摘要

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.