数学基礎論のプログラミング言語理論への応用

今年度の最初の成果としては、現在プログラム言語理論や並列アルゴリズムといった分野から注目されている線型論理(linear logic)の、非可換な体系についての研究をさらに進めたことである。昨年度の岡田光弘(慶應大)との共同研究によってNon-commutative proof netのCharacterization Theoremを得たが、この研究においては、Non-commutative Linear logicの特徴づけとしてStrong Planarityとstack conditionによって定められるmarked Danos-regnier graphのサブクラスという新しい概念を定義した。strong planarityという概念は、結び目理論におけるRidemeister Moveを用いてplanar graphの交差を取り除く方法を分析し、その結果として得られた概念である。これらの結果をさらにAbrusciのNon-commutative Linear LogicやIntuitionistic Linear LogicのCharacterization Theoremへと応用することができた。現在進めている研究では、より計算量の少ないNon-commutative Linear Logicの特徴づけを与えようとしている。今まで得られていたNon-commutative proof netの特徴づけは、全てCommutative proof netであることが条件であり、Non-commutative proof netの方がgraphとしては単純になっているにもかかわらず、最良の場合でも、少なくともCommutative proof netの判定に使われる計算量が必要であった。今、取り組んでいる定理では、交差のないgraph(plane graph)が与えられたとして、Commutative proof netであることを条件とせず、graphのlinkの位置関係と、L-only subgraphとR-only subgraphという二つのsubgraphから、直接Non-commutative proof netであるかどうか判定できる。今後このCharacterization Theormの理論的な計算量についてさらに考察を進めていくつもりである。

今年度の最初の成果としては、現在プログラム言語理論や並列アルゴリズムといった分野から注目されている線型論理(linear logic)の、非可換な体系についての研究をさらに進めたことである。昨年度の岡田光弘(慶應大)との共同研究によってNon-commutative proof netのCharacterization Theoremを得たが、この研究においては、Non-commutative Linear logicの特徴づけとしてStrong Planarityとstack conditionによって定められるmarked Danos-regnier graphのサブクラスという新しい概念を定義した。strong planarityという概念は、結び目理論におけるRidemeister Moveを用いてplanar graphの交差を取り除く方法を分析し、その結果として得られた概念である。これらの結果をさらにAbrusciのNon-commutative Linear LogicやIntuitionistic Linear LogicのCharacterization Theoremへと応用することができた。現在進めている研究では、より計算量の少ないNon-commutative Linear Logicの特徴づけを与えようとしている。今まで得られていたNon-commutative proof netの特徴づけは、全てCommutative proof netであることが条件であり、Non-commutative proof netの方がgraphとしては単純になっているにもかかわらず、最良の場合でも、少なくともCommutative proof netの判定に使われる計算量が必要であった。今、取り組んでいる定理では、交差のないgraph(plane graph)が与えられたとして、Commutative proof netであることを条件とせず、graphのlinkの位置関係と、L-only subgraphとR-only subgraphという二つのsubgraphから、直接Non-commutative proof netであるかどうか判定できる。今後このCharacterization Theormの理論的な計算量についてさらに考察を進めていくつもりである。