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

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

• 批准号: 04044150
• 负责人: 伊藤 正美
• 金额: $ 2.88万
• 依托单位: Kyoto Sangyo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for international Scientific Research
• 财政年份: 1992
• 资助国家: 日本
• 起止时间: 1992 至 1993
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04044150/
• 关键词: 文脈自由言語; 正規言語; Pumping Lemma; 自由単位半群; Shuffle積; 語の書換え系; ω-語; コード

形式言語の研究については、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の特別号として出版される。

The study of formal speech is based on the use of dense context, free speech and formal speech structure. Ito, Katsuyoshi and Yu jointly studied the degree of understanding and achievements. At the end of August this year, the International Conference FCT'93 was held in Szeged City. Ito, Thierrin and Reis Semigroup Adherence Research on the Application of Free Semigroup Theory to Predetermined Cases, the Results of which were published in February this year by the International Society for Combinatorics,Graph Theory and Computing. Ito, Thierrin speech Shuffle product results, the opening of the International Conference Automata and Programming Languages Ito, Thierrin speech The results of the generalization of abstract algebra of Shuffle product by Kobayashi and Katsuyoshi were published in the International Journal Theoretical Computer Science (Elsevier). The joint study of language and language began yesterday. The study of algebraic structure of maximal Solid codes begins at the right moment. The Second Colloquium on Words,Languages and Combinatorics was held from August 25 to 28, 2009. The results were published in Proceedings of World Scientific Society and Special Issue of Theoretical Computer Science of Elsevier Society

项目成果

M.Ito: "Disjunctive and dense properties of languages" Lecture Notes in Computer Science(Springer-Verlag,New York)(Invited paper at FCT'93). (1993)

M.Ito：“语言的析取和稠密属性”计算机科学讲义（Springer-Verlag，纽约）（FCT93 特邀论文）。

M.Ito(Guest editor): "Theoretical Computer Science 108(1)" Elsevier Science Publishers(Amsterdam), 183 (1993)

M.Ito（客座编辑）：《理论计算机科学 108(1)》Elsevier Science Publishers（阿姆斯特丹），183 (1993)

M.Katsura: "The schuffle algebra and its derivations" Theoretical Computer Science(Elsevier Science Publishers,Amsterdam). (1993)

M.Katsura：“Schuffle 代数及其推导”理论计算机科学（Elsevier Science Publishers，阿姆斯特丹）。

M.Ito(Editor): "Words,Languages and Combinatorics" World Scientific Publ.Co Pte Ltd(Singapore), 590 (1992)

M.Ito（编辑）：“Words、Languages and Combinatorics” World Scientific Publ.Co Pte Ltd（新加坡），590 (1992)

M.Ito(Guest editor): "Special Issue of Theoretical Computer Science" Elsevier Science Publishers(Amsterdam), (1995)

M.Ito（客座编辑）：“理论计算机科学特刊”Elsevier Science Publishers（阿姆斯特丹），（1995）