解析関手と理論計算機科学

分析函子和理论计算机科学

• 批准号: 09780242
• 负责人: 長谷川 立
• 金额: $ 1.28万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780242/
• 关键词: 解析関手; ラムダ計算; 項書き換え系; 不動点; Kruskalの定理

ラムダ計算の不動点演算子と,解析や数え上げ組み合わせ論に現れるLagroge-Goodの公式との,関連を調べた.この公式は,形式的幕級数の逆関数を計算するときや,木構造の数え上げの問題などに用いられる式で,ある種の不動点を計算するものである.また,ラムダ計算の不動点演算子は,再帰的呼び出しをもつ関数プログラムをラムダ計算の中で表現するのに用いられる.本年の研究では,ラムダ計算のモデル論を用いて,Lagrange-Goodの公式の別証を与えることを行った.既存の証明としては,留数を用いたものや,数え上げ組み合わせ論を用いたものが知られているが,今回の結果は,まったく異なったアプローチによっていて,理論計算機科学の中で得られた結果を用いている.特に,最近知られるようになった,ラムダ計算の不動点演算子と,トレースとの関係を有効に用いている.この研究の意義は,理論計算機科学と,解析学や数え上げ組み合わせ論というまったく異なる分野に現れる不動点が密接に結びついていることを示した点にあるといえよう.これらを結びつけるのに用いた道具が解析関手である.この結果は,1998年8月にチェコ共和国のBrnoで開かれた国際会議Fixpointsin Computer Scienceで発表された.また,1999年1月に京都大学でひらかれた短期共同研究「二階算術の諸体系の研究」で,詳細な解説を行った.前年の成果とあわせて書かれた論文が,Theoretical Computer Science誌に投稿中である.

The fixed point algorithm of the calculation is based on the Lagroge-Good equation. The formula is used to calculate the inverse relation number of the exponential series of the form, and the number of the tree structure is used to calculate the fixed point of the tree structure. In addition, the fixed point algorithm of the first class calculation is used in the performance of the second class calculation. This year's research is to prove the Lagrange-Good formula by using the Lagrange-Good formula. The result of the experiment is that the computer science has a lot of advantages and disadvantages. In particular, the most recent knowledge of the fixed point algorithm, the most recent knowledge of the fixed point algorithm, the most recent knowledge of the fixed point algorithm. The significance of this research is theoretical computer science, analytical science, and mathematical theory. It's too late to use the props to analyze and close the hand. The result was that in August 1998, the Republic of Korea held an international conference on Fixpointsin Computer Science. January 1999 Kyoto University short-term joint research,"Research on systems of second-order arithmetic," detailed explanation. The previous year's achievements were published in the journal Theoretical Computer Science.

项目成果

R.Hasegawa: "An analysis of divisibility ordenngs and recursive path orderings" Lecture Notes in Computer Science(Springer). 1345. 283-296 (1997)

R.Hasekawa：“可分性排序和递归路径排序的分析”计算机科学讲义（Springer）。