Descriptional complexity of finite-state machines
有限状态机的描述复杂性
基本信息
- 批准号:217321-2008
- 负责人:
- 金额:$ 1.68万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2010
- 资助国家:加拿大
- 起止时间:2010-01-01 至 2011-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
My research on finite-state machines is part of the theory of computing. Algorithms based on finite-state machines are used in practically all areas of computing, from natural language processing to software verification. My work deals with lower bounds for the size of finite-state machines. This area of research is called descriptional complexity. When we have an implementation of a finite-state machine for a problem P, this gives an upper bound for the descriptional complexity of P. However, the crucial task is to establish lower bounds, that is, we have to prove that no machine of smaller size can solve the problem. Work on descriptional complexity contributes to our understanding of fundamental questions on the difficulty of computational problems. Descriptional complexity has recently become more important also from an applications point of view since finite-state machines used in natural language processing may require millions of states.
我对有限状态机的研究是计算理论的一部分。基于有限状态机的算法被用于几乎所有的计算领域,从自然语言处理到软件验证。我的工作涉及有限状态机大小的下限。这一研究领域被称为概念复杂性。当我们有一个问题P的有限状态机的实现时,这给出了P的计算复杂度的上限,然而,关键的任务是建立下限,也就是说,我们必须证明没有更小尺寸的机器可以解决这个问题。描述复杂性方面的工作有助于我们理解计算问题难度的基本问题。描述复杂性最近变得更加重要,从应用的角度来看,因为在自然语言处理中使用的有限状态机可能需要数百万个状态。
项目成果
期刊论文数量(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
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2021
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2020
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2019
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Finite-state machines and their extensions: Foundational questions and applications
有限状态机及其扩展:基础问题和应用
- 批准号:
RGPIN-2018-04110 - 财政年份:2018
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2017
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2016
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2015
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2014
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Automata with limited nondeterminism and applications of automata
有限非确定性自动机及其应用
- 批准号:
217321-2013 - 财政年份:2013
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
CAREER: Three-manifolds with finite volume, their geometry, representations, and complexity
职业:有限体积的三流形、它们的几何形状、表示形式和复杂性
- 批准号:
2142487 - 财政年份:2022
- 资助金额:
$ 1.68万 - 项目类别:
Continuing Grant
Finite Decomposition Complexity and Thompson group F
有限分解复杂性和 Thompson F 群
- 批准号:
551404-2020 - 财政年份:2020
- 资助金额:
$ 1.68万 - 项目类别:
University Undergraduate Student Research Awards
Combinatorial homotopy theory of spaces and applications to sensor network using categories
空间组合同伦理论及其在传感器网络中的应用
- 批准号:
17K14183 - 财政年份:2017
- 资助金额:
$ 1.68万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
Finite-length analysis with computation complexity
计算复杂度有限长度分析
- 批准号:
17H01280 - 财政年份:2017
- 资助金额:
$ 1.68万 - 项目类别:
Grant-in-Aid for Scientific Research (A)
Structural Complexity of Finite and Infinite Computations
有限和无限计算的结构复杂性
- 批准号:
233251376 - 财政年份:2013
- 资助金额:
$ 1.68万 - 项目类别:
Research Grants
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2012
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2011
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual
An Analysis of Finite-State Complexity
有限状态复杂性分析
- 批准号:
409295-2011 - 财政年份:2011
- 资助金额:
$ 1.68万 - 项目类别:
Alexander Graham Bell Canada Graduate Scholarships - Master's
Complexity in Algebra and Algebra in Complexity: the role of finite semigroups and general algebra
代数中的复杂性和复杂中的代数:有限半群和一般代数的作用
- 批准号:
DP1094578 - 财政年份:2010
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Projects
Descriptional complexity of finite-state machines
有限状态机的描述复杂性
- 批准号:
217321-2008 - 财政年份:2009
- 资助金额:
$ 1.68万 - 项目类别:
Discovery Grants Program - Individual