このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

全体的な構造と定式化

  1. ソフトウェア的な技法
  2. 圏論的な解釈
  3. 論理計算
  4. ラムダ計算
  5. 具体的なモデル

ソフトウェア的な技法としては、とりあえずはコンベンションと動的(実行時)演算ライブラリだけを準備して、徒手空拳でも使えることをアピールしよう。もちろん、コンテナ(自動的な生成/初期化/ワイヤリング)、シェル(対話的な操作環境)、デザインツールがあったほうが便利なんだけど手が回らん。

圏論としては、トレース付きモノイド圏とそのInt構成であるコンパクト閉圏が基本。ただし、多圏を使った方が見通しがいいことがわかったので、トレース付きモノイド多圏、コンパクト閉多圏を入れたい。Cがトレース付きモノイド圏だとして、D = Int(C)、さらに多圏Poly(C)、Poly(D) = Poly(Int(C)) = Int(Poly(C)) を考える。ひょっとすると、ステファネスクが構想するdoubly-traced semiringal categoryが出てくるのかも知れない。

多圏化するときには、列(sequence, string)多圏だけでなくレコード多圏も必要で、対称亜群(symmetric groupoid)が働く対称多圏と同様に、改名亜群(renaming/permutation groupoid)が働く亜群作用付き多圏を定義しておくとよさそう。亜群作用の部分が、コネクター(と呼ばれるもの)になる。

論理計算は、基本的にPoly(Int(C))をモデルとするシーケント計算。最終的には、トレース付きモノイド圏/コンパクト閉圏での解釈をする。線形論理の部分系になるだろうが、どんな部分系かはよくわからん。

ラムダ計算は、コンパクト閉圏上のウエス(上江州)計算となるだろう。ベースとして、(CCCとは限らない)モノイド閉圏におけるラムダ計算が必要。閉性からf:A,B→Cのカリー化f^:A→[B,C]は定義できるが、変数を伴ったラムダ抽象をうまく定義するにはウエス・トリックが必要そうだ。

具体的なモデルは、ラベル付き遷移系の拡張である遷移変換系(トランスデューサ)の圏だ。これは、一種の対話圏(interaction category)だろう。この圏は、荷電境界付きグラフの圏と深く関係しているはずだ。それを拡張オートマトンとみなせば(例えばXMLの)構文論とも繋がると思われる。