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

有限状态机或有限自动机是一种抽象的计算模型，其中状态转换由当前状态和下一个输入字符确定。 有限自动机识别正则语言的类别，并且由于它们的简单性和易于实现，正则语言有许多应用，例如，在自然语言处理和程序验证中。描述复杂性是指如何简洁地指定某些对象，如有限自动机。拥有简洁的对象将改善我们对软件的控制，这将变得更有效，更容易验证。为了更深入地了解计算的复杂性，我们需要建立下限，也就是说，证明没有状态更少的机器可以识别给定的语言。该提案的工作重点是研究有限自动机及其扩展（如可见下推机）的概念复杂性或状态复杂性。所提出的工作的一个主要方向涉及错误检测的状态复杂性。字符串或符号序列用于表示不同类型的对象。通过定义字符串上的距离度量，我们可以形式化对象之间的接近度的概念。字符串u和v的编辑距离计算将字符串u转换为v所需的最小插入、删除和替换操作次数。语言L的邻域由所有与L的某个字符串的距离最多为r的字符串组成，其中r是邻域的半径。编辑距离，以及其他常用的字符串距离度量，是正则性保持的，因为正则语言的邻域总是正则的，也就是说，可以被有限自动机识别。插入、删除和替换可以被视为通信信道上的错误，对于错误检测和错误校正应用，关键问题是需要多大的有限自动机来识别L的邻域（作为L的最小自动机的状态数的函数）。由于求补不改变确定性有限自动机（DFA）的大小，所以对于半径为r的L的邻域，最小DFA的大小等于距离L的任何字符串至少为r+1的字符串集合的状态复杂度。半径为r的邻域的DFA的最佳大小可以被视为引入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.