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

有限状态机或有限自动机是一种抽象的计算模型，其中状态转换由当前状态和下一个输入字符确定。有限自动机识别正则语言的类，由于其简单性和易于实现，正则语言在自然语言处理和程序验证中有许多应用。描述复杂性涉及如何简洁地指定某些对象，例如有限自动机。拥有简洁的对象将改善我们对软件的控制，从而变得更高效和更容易验证。为了更深入地了解计算的复杂性，我们需要建立下界，即证明任何状态较少的机器都不能识别给定的语言。该方案的工作集中于研究有限自动机及其扩展，如可视下推机器的描述复杂性或状态复杂性，其中一个主要方向是错误检测的状态复杂性。字符串或符号序列用于表示不同类型的对象。通过定义字符串上的距离度量，我们可以形式化对象之间距离的概念。字符串u和v的编辑距离计算将字符串u转换为v所需的最小数目的插入、删除和替换操作。语言的邻域L由与L的某个字符串的距离至多为r的所有字符串组成，其中r是邻域的半径。编辑距离以及其他常用的字符串距离度量都是正则性保持的，因为规则语言的邻域总是规则的，也就是说，可以由有限自动机识别。这些插入、删除和替换可以视为通信通道上的错误，对于错误检测和纠错应用，关键问题是需要多大的有限自动机来识别L(作为L极小自动机状态数的函数)的邻域。由于取补不改变确定性有限自动机的大小，因此半径为r的L邻域的最小有限自动机的大小等于距离至少为r+1的字符串集合的状态复杂度。半径为r的邻域的最优有限自动机的大小可以看作是在引入r个差错的信道上进行错误检测的状态复杂度。由于现代应用需要非常大的有限自动机，所以彻底了解它们的描述复杂性是很重要的。相关算法工作的目标是设计有效的算法来计算(常规)语言之间的距离。在五年期间申请的资金将支持6名博士、6名硕士和5名本科生的研究活动。

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.