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

有限状态机及其扩展：基础问题和应用

• 批准号: RGPIN-2018-04110
• 负责人: Salomaa, Kai
• 金额: $ 3.5万
• 依托单位: Queen's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=664165
• 关键词: Finite; state; machines; their; extensions

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.

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