計算理論の数学的基礎の研究

計算理論の数学的基礎の研究として,研究代表者はとくに無限語とその上のオ-トマトンについて、いままでえられた結果(既発表の分も含む)を統一的にまとめ、発表した。そこでは,ω言語(無限語の集合)のさまざまなクラスに対し、単項2階述語論理式による特徴付け,有限状態オ-トマトンによる特徴付け、ω正則表現による特徴付け,の関連を統一的に論じた。これにより,ω正則言語と呼ばれるクラスの内部構造について,かなり明らかにされてきたと考えている。ここで,論理式は,例えば無限に計算を続けるシステムに対する制約条件などを記述する道具となるものである。一方,オ-トマトンはそのようなシステムの数学的モデルであり,ω正則表現はシステムの可能な無限動作の集合に対し,直観的に理解しやすい表現を与えるものである。ω正則言語という限られたクラスとはいえ,これらの関連が明確にされることにより,無限に計算を続けるシステムと,その無限計算に関する理解が深まるものと思われる。研究のもう1つの柱としてかかげた並列計算を扱う数学的モデルの研究については,今回とくに発表をするまでまとめることはできなかったが,研究は継続しており、こずれ機会を見て発表する予定である。今回の科研費の援助により,各研究分担者はそれぞれの専攻分野に関する研究集会に参加し,他大学の研究者と有効な研究交流を行うとともに,本研究に関連のある成果をまとめている。詳細は省略するが,研究発表の欄に発表された論文を掲げておく。

計算理論の数学的基礎の研究として,研究代表者はとくに無限語とその上のオ-トマトンについて、いままでえられた結果(既発表の分も含む)を統一的にまとめ、発表した。そこでは,ω言語(無限語の集合)のさまざまなクラスに対し、単項2階述語論理式による特徴付け,有限状態オ-トマトンによる特徴付け、ω正則表現による特徴付け,の関連を統一的に論じた。これにより,ω正則言語と呼ばれるクラスの内部構造について,かなり明らかにされてきたと考えている。ここで,論理式は,例えば無限に計算を続けるシステムに対する制約条件などを記述する道具となるものである。一方,オ-トマトンはそのようなシステムの数学的モデルであり,ω正則表現はシステムの可能な無限動作の集合に対し,直観的に理解しやすい表現を与えるものである。ω正則言語という限られたクラスとはいえ,これらの関連が明確にされることにより,無限に計算を続けるシステムと,その無限計算に関する理解が深まるものと思われる。研究のもう1つの柱としてかかげた並列計算を扱う数学的モデルの研究については,今回とくに発表をするまでまとめることはできなかったが,研究は継続しており、こずれ機会を見て発表する予定である。今回の科研費の援助により,各研究分担者はそれぞれの専攻分野に関する研究集会に参加し,他大学の研究者と有効な研究交流を行うとともに,本研究に関連のある成果をまとめている。詳細は省略するが,研究発表の欄に発表された論文を掲げておく。