Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
基本信息
- 批准号:RGPIN-2018-04110
- 负责人:
- 金额:$ 3.5万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2020
- 资助国家:加拿大
- 起止时间:2020-01-01 至 2021-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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名本科生的研究活动。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Salomaa, Kai其他文献
Finite-State Complexity and the Size of Transducers
- DOI:
10.4204/eptcs.31.6 - 发表时间:
2010-01-01 - 期刊:
- 影响因子:0
- 作者:
Calude, Cristian S.;Salomaa, Kai;Roblot, Tania K. - 通讯作者:
Roblot, Tania K.
Finite state complexity
- DOI:
10.1016/j.tcs.2011.06.021 - 发表时间:
2011-09-23 - 期刊:
- 影响因子:1.1
- 作者:
Calude, Cristian S.;Salomaa, Kai;Roblot, Tania K. - 通讯作者:
Roblot, Tania K.
STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
- DOI:
10.1142/s0129054112400035 - 发表时间:
2012-01-01 - 期刊:
- 影响因子:0.8
- 作者:
Calude, Cristian S.;Salomaa, Kai;Roblot, Tania K. - 通讯作者:
Roblot, Tania K.
THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
- DOI:
10.1142/s0129054113400315 - 发表时间:
2013-11-01 - 期刊:
- 影响因子:0.8
- 作者:
Han, Yo-Sub;Ko, Sang-Ki;Salomaa, Kai - 通讯作者:
Salomaa, Kai
State Complexity of Neighbourhoods and Approximate Pattern Matching
- DOI:
10.1142/s0129054118400099 - 发表时间:
2018-02-01 - 期刊:
- 影响因子:0.8
- 作者:
Ng, Timothy;Rappaport, David;Salomaa, Kai - 通讯作者:
Salomaa, Kai
Salomaa, Kai的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Salomaa, Kai', 18)}}的其他基金
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2019
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2015
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2014
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2013
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2012
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
Simulation and certification of the ground state of many-body systems on quantum simulators
- 批准号:
- 批准年份:2020
- 资助金额:40 万元
- 项目类别:
Cortical control of internal state in the insular cortex-claustrum region
- 批准号:
- 批准年份:2020
- 资助金额:25 万元
- 项目类别:
微波有源Scattering dark state粒子的理论及应用研究
- 批准号:61701437
- 批准年份:2017
- 资助金额:28.0 万元
- 项目类别:青年科学基金项目
超导量子器件中关于量子计算、电路量子电动力学和退相干的研究
- 批准号:11174248
- 批准年份:2011
- 资助金额:75.0 万元
- 项目类别:面上项目
拓扑绝缘体中的强关联现象
- 批准号:11047126
- 批准年份:2010
- 资助金额:4.0 万元
- 项目类别:专项基金项目
分子高振动-转动激发态结构中的复杂相互作用
- 批准号:11074204
- 批准年份:2010
- 资助金额:38.0 万元
- 项目类别:面上项目
以硫氧还蛋白还原酶为靶点的化学生物学研究
- 批准号:21002047
- 批准年份:2010
- 资助金额:19.0 万元
- 项目类别:青年科学基金项目
激光催化下的旋量凝聚原子:自旋混合与共振拍
- 批准号:10974045
- 批准年份:2009
- 资助金额:34.0 万元
- 项目类别:面上项目
基于SSD的大规模元数据处理技术研究
- 批准号:60970025
- 批准年份:2009
- 资助金额:30.0 万元
- 项目类别:面上项目
李超代数的表示和仿射李代数的VCS表示及双代数结构
- 批准号:10901028
- 批准年份:2009
- 资助金额:17.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Transforming regular expressions to finite-state machines
将正则表达式转换为有限状态机
- 批准号:
563494-2021 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
University Undergraduate Student Research Awards
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2019
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
EAGER: Teaching Computational Thinking through Programming Wearable Devices as Finite State Machines
EAGER:通过将可穿戴设备编程为有限状态机来教授计算思维
- 批准号:
1647023 - 财政年份:2016
- 资助金额:
$ 3.5万 - 项目类别:
Standard Grant
Quantifying Nondeterminism in Finite State Machines
量化有限状态机中的不确定性
- 批准号:
476202-2015 - 财政年份:2015
- 资助金额:
$ 3.5万 - 项目类别:
Alexander Graham Bell Canada Graduate Scholarships - Doctoral
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2012
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2011
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2010
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual