形式言語上の演算の研究

形式语言运算研究

基本信息

批准号：
07F07810
负责人：
伊藤正美
金额：
$ 1.47万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2009
项目状态：
已结题

项目摘要

外国人特別研究員は、DNAの複製の数学的モデルとしての語の上の複製演算uvw→uvvw、その逆演算uvvw→uvw、それらの閉包演算等の研究を行いました。とくに、チョムスキー言語階層(正規言語類や文脈自由言語類)のこれらの演算による保存性の研究が主要なテーマでした。研究成果は、国際専門誌Natural ComputingやLecture Notes in Computer Science(Springer, Berlin)に掲載されました。さらにDNAの二重螺旋の捩じれによる破損とその修復の数学的モデルである語の上の有界なヘアピン演算の完備化の研究を、受入研究者およびV.Mitrana教授との共同研究として行いました。研究成果は、Lecture Notes in Computer Science等に掲載されました。また、プッシュダウンオートマトンの一般化である深層プッシュダウンオートマトンが受理する言語とほかの言語、たとえばマトリックス言語等との比較等、深層プッシュダウンオートマトンが受理する言語が属する言語階層の研究を行いました。この研究の一部は、A.Meduna教授との共同研究として行われました。研究成果は、国際ワークショップAFLASのProceedingsのAutomata, Formal Languages and Algebraic Systems(World Scientific, Singapore)に掲載されます。外国人特別研究員のそのほかの研究成果としましては、外部観測計算のメカニズムの研究と計算量の研究があります。これらの研究成果は複数の国際会議で発表されました。

外国研究人员对单词作为DNA复制模型的单词进行了复制操作进行了研究，并进行了UVVW→UVW的逆操作以及这些逆操作。特别是，主题是研究乔姆斯基语言层次结构（普通语言和无上下文语言）的可靠性。研究结果发表在《计算机科学》（柏林施普林格）的国际期刊《自然计算和讲义》中。此外，我们与主持人研究人员和Mitrana教授进行了联合研究，研究了该单词上方有限的发夹操作的完成，这是一种用于扭转损伤及其修复的数学模型。研究结果发表在计算机科学和其他地方的讲义上。我们还对深层俯卧撑自动机所接受的语言层次结构进行了研究，例如将深度下降自动机接受的语言与其他语言（例如矩阵语言）进行比较。这项研究的一部分是与A. Meduna教授合作进行的。该研究结果将以自动机，正式语言和代数系统（世界科学，新加坡）的诉讼，国际研讨会。外国特别研究人员的其他研究结果包括研究外部观察计算机制和计算的复杂性。这些发现是在几个国际会议上提出的。