半群・形式言語および語の組合せ論

半群/形式语言和单词组合学

基本信息

批准号：
04044150
负责人：
伊藤正美
金额：
$ 2.88万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for international Scientific Research
财政年份：
1992
资助国家：
日本
起止时间：
1992 至 1993
项目状态：
已结题

项目摘要

形式言語の研究については、Pumping Lemmaを利用した稠密な文脈自由言語および正規言語の構造が伊藤、勝良、Yuによる共同研究によりかなりの程度解明され、その成果が本年8月末にハンガリー・Szeged市で開催される国際会議FCT'93において伊藤による招待講演のかたちで発表される。伊藤、ThierrinおよびReisによる半群のAdherenceに関する研究は特に自由単位半群に適用した場合の理論の精密化が当初の予定どおりをはかられ、この結果は本年2月に米国フロリダ州Boca Raton市で開催された国際学会Combinatorics,Graph Theory and Computingで伊藤により発表された。伊藤、Thierrinによる言語のShuffle積の結果は、ハンガリー・サルゴタルジャン市で開催される国際会議Automata and Programming Languagesにおいて伊藤により招待講演のかたちで発表される。小林、勝良によるShuffle積の抽象代数的一般化についての結果は国際専門誌Theoretical ComputerScience(Elsevier社)に掲載される。語の書換え系およびω-語の共同研究は、昨夏の小林のカナダ滞在中にJurgensenとの共同研究が開始された。勝良は、カナダ滞在を契機にJurgensenと極大なSolid codesの代数的な構造の研究を開始した。以上が平成4年度中になされた共同研究の内容および経過であるが、それ以外の事業として両国のメンバーを組織委員として昨年8月25日-28日の期間に国際会議The Second Colloquium on Words,Languages and Combinatorics、および8月29日-31日にワークショップが開催された。その成果はWorld Scientific社よりProceedingsとして、またElsevier社よりTheoretical Computer Scienceの特別号として出版される。

关于形式语言的研究，通过伊藤、葛城和宇的联合研究，密集上下文无关语言和使用泵引理的常规语言的结构已经在相当程度上得到阐明，并在年底公布了结果今年 8 月在匈牙利塞格德举行的国际会议 FCT'93 上，伊藤将作为邀请演讲进行演讲。 Ito、Thierrin 和 Reis 对半群依从性的研究成功地完善了该理论，特别是按照原计划应用于自由单位半群，其结果于今年 2 月在美国佛罗里达州博卡拉顿发表。是由伊藤在该市举办的国际会议组合学、图论和计算上提出的。 Ito 和 Thierrin 的语言洗牌产品的结果将以邀请演讲的形式在匈牙利 Sargotarcan 举行的自动机和编程语言国际会议上展示。小林和桂对Shuffle乘积的抽象代数推广结果将发表在国际期刊《理论计算机科学》（Elsevier）上。去年夏天，小林与尤尔根森在加拿大逗留期间，开始了关于单词重写系统和 ω-单词的合作研究。在加拿大期间，桂开始与尤尔根森一起研究极端固体码的代数结构。以上是1992年联合研究的内容和进展，除此之外，去年8月25日至28日还举行了由两国成员担任组委会的国际会议——第二届文字学术讨论会语言和组合学以及研讨会于 8 月 29 日至 31 日举行。研究结果将由《世界科学报》和《爱思唯尔》作为《理论计算机科学》特刊发表。