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

点击翻译按钮获取中文摘要

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