Finite-state machines and their extensions: Foundational questions and applications

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

A finite-state machine, or a finite automaton, is an abstract model of computation where state transitions are determined by the current state and the next input character. Finite automata recognize the class of regular languages and, due to their simplicity and ease of implementation, regular languages have many applications, for example, in natural language processing and program verification. Descriptional complexity is concerned with how succinctly certain objects, such as finite automata, can be specified. Having succinct objects will improve our control of software which becomes more efficient and easier to verify. In order to gain deeper insights into the complexity of computation we need to establish lower bounds, that is, to prove that no machine with fewer states can recognize a given language. The work of the proposal focuses on studying the descriptional complexity, or state complexity, of finite automata and their extensions, such as visibly pushdown machines.One major direction of the proposed work deals with the state complexity of error detection. Strings, or sequences of symbols, are used to represent different kinds of objects. By defining a distance measure on strings we can formalize the notion of closeness between the objects. The edit distance of strings u and v counts the smallest number of insertion, deletion and substitution operations that are needed to transform the string u into v. A neighborhood of a language L consists of all strings that have distance at most r from some string of L where r is the radius of the neighborhood. The edit distance, as well as other commonly used string distance measures, are regularity preserving in the sense that a neighborhood of a regular language is always regular, that is, can be recognized by a finite automaton. The insertions, deletions and substitutions can be viewed as errors on a communication channel and for error detection and error correction applications the crucial question is how large a finite automaton is needed to recognize a neighborhood of L (as a function of the number of states of the minimal automaton for L). Since complementation does not change the size of a deterministic finite automaton (DFA), the size of the minimal DFA for the neighborhood of L having radius r is equal to the state complexity of the set of strings that have distance at least r+1 from any string of L. The optimal size of a DFA for a neighborhood of radius r can be viewed as the state complexity of error detection on a channel that introduces r errors. Due to modern applications that require finite automata of very large size, a thorough understanding of their descriptional complexity is important. The goal of related algorithmic work is to design efficient algorithms to compute the distance between (regular) languages.The requested funding over the five year period will support the research activity of 6 PhD, 6 MSc and 5 undergraduate students.