形式言語とオートマトン

研究分担者は、平成17年度中に2つの論文を公刊した。一つはThe language of primitive words is not regular : two simple proofsで、原始語全体からなる言語が正規言語にならないことの2つの新しい証明である。二つ目はOn products of primitive wordsで原始語の連接に関するLyndon-Schutzenbergerの定理、およびShyr-Yuの定理の新しい証明を与えている。研究代表者は平成17年度中に3つの論文を公刊している。論文の一つはOn regular languages determined by nondeterministic directable automataで非決定性有向オートマトンの有向語のなす言語の性質と言語族間の包含関係を調べている。二つ目はCommutative closure of languagesでスレンダー文脈自由言語の可換閉包が文脈自由言語になるための必要十分条件を与えている。三つ目はDeterministic and nondeterministic directable automataで決定性および非決定性有向オートマトンに関するサーベイ論文である。研究代表者と研究分担者の共同研究である3種類の周期性をもつ文と関連した言語とマルクス文脈言語の関係に関する研究成果はSome periodicity of words and Marcus contextual grammarsとして京都大学数理解析研究所の共同研究集会に於いて発表された。そのほかの活動としては、研究代表者は研究分担者と協力して数回のワークショップを開催した。また国外から著名な研究者であるAttila Pethoe教授(ハンガリー共和国)およびAlexander Meduna教授(チェコ共和国)を招き研究情報の提供を受けるとともに共同研究を開始した。

研究分担者は、平成17年度中に2つの論文を公刊した。一つはThe language of primitive words is not regular : two simple proofsで、原始語全体からなる言語が正規言語にならないことの2つの新しい証明である。二つ目はOn products of primitive wordsで原始語の連接に関するLyndon-Schutzenbergerの定理、およびShyr-Yuの定理の新しい証明を与えている。研究代表者は平成17年度中に3つの論文を公刊している。論文の一つはOn regular languages determined by nondeterministic directable automataで非決定性有向オートマトンの有向語のなす言語の性質と言語族間の包含関係を調べている。二つ目はCommutative closure of languagesでスレンダー文脈自由言語の可換閉包が文脈自由言語になるための必要十分条件を与えている。三つ目はDeterministic and nondeterministic directable automataで決定性および非決定性有向オートマトンに関するサーベイ論文である。研究代表者と研究分担者の共同研究である3種類の周期性をもつ文と関連した言語とマルクス文脈言語の関係に関する研究成果はSome periodicity of words and Marcus contextual grammarsとして京都大学数理解析研究所の共同研究集会に於いて発表された。そのほかの活動としては、研究代表者は研究分担者と協力して数回のワークショップを開催した。また国外から著名な研究者であるAttila Pethoe教授(ハンガリー共和国)およびAlexander Meduna教授(チェコ共和国)を招き研究情報の提供を受けるとともに共同研究を開始した。