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.的所有子自动，此外，我们建立了自动机结构与其层集合之间的关系。 2）我们对文字和语言进行了几项操作。特别是，主要完成了对语言重复封闭的研究。我们表明，任何无上下文的语言的K限制重复封闭都变得无上下文，但是常规语言的K限制重复封闭并不一定变得规律。我们提供了一些条件，以使给定的常规语言重复封闭是常规的。 3）关于非常规计算理论的研究，给出了Grover算法的修订版。

项目成果

Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters

• DOI: 10.1007/s11128-012-0498-0
• 发表时间: 2013-05-01
• 期刊: QUANTUM INFORMATION PROCESSING
• 影响因子: 2.5
• 作者: Toyama, F. M.;van Dijk, W.;Nogami, Y.
• 通讯作者: Nogami, Y.

On Chomsky hierarchy of palindromic languages

论回文语言的乔姆斯基层次

• 发表时间: 2012
• 期刊: 数理解析研究所構究録
• 作者: P. Domosi;Sz. Fazekas;M. Ito
• 通讯作者: M. Ito

K-restricted duplication closure of languages

语言的 K 限制重复闭包

• 发表时间: 2011
• 期刊: Proceedings of AFL 2011, Edited by P. Domosi and Sz. Ivan (Debrecen, Hungary)
• 作者: 小林靖明;玉木久夫;M. Ito
• 通讯作者: M. Ito

Bounded hairpin completion

有界发夹完成

• 发表时间: 2011
• 期刊: Information and Computation
• 影响因子: 1
• 作者: M. Ito;P. Leupold;F. Manea;V. Mitrana
• 通讯作者: V. Mitrana

Context-Free Languages and Primitive Words

上下文无关语言和原始单词

• 发表时间: 2014
• 作者: P. Domosi;M. Ito
• 通讯作者: M. Ito