权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Automata, Formal languages and Computation

自动机、形式语言和计算

基本信息

批准号：
23500027
负责人：
ITO Masami
金额：
$ 2.5万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2011
资助国家：
日本
起止时间：
2011 至 2013
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500027/
关键词：
オートマトンの代数的構造オートマトンの状態の層オートマトンの自己同型群重複閉包演算有界重複閉包文脈自由言語正規言語量子探索アルゴリズムプッシュダウンオートマトン部分オートマトン半束群行列型オートマトン調和振動子言語階層位相整合法回文量子アルゴリズム

项目摘要

1) We investigated the algebraic structures of automata. Especially, we introduced the notion of layers of an automaton A which forms a partially ordered set and determined all sub-automata of A. Furthermore, we established a relationship between the structure of an automaton and the set of its layers. 2) We investigated several operations on words and languages. Especially, the study of duplication closures of languages was mainly done. We showed that the K-restricted duplication closure of any context-free language becomes context-free but the K-restricted duplication closure of a regular language does not necessarily become regular. We provided some conditions for the duplication closure of a given regular language to be regular. 3) Regarding the study on the unconventional computation theory, a revised version of the Grover's algorithm was given.

1)研究了自动机的代数结构。特别地，我们引入了自动机A的层的概念，它构成了一个部分有序集，并决定了A的所有子自动机，并且我们建立了自动机的结构与其层集之间的关系。我们研究了几种关于单词和语言的操作。特别是对语言的重复闭包进行了研究。我们证明了任何上下文自由语言的k限制复制闭包成为上下文自由的，但规则语言的k限制复制闭包不一定成为规则的。我们为给定正则语言的重复闭包是正则的提供了一些条件。3)针对非常规计算理论的研究，给出了Grover算法的修正版本。