プログラムの実行であるラン T→S が、ラベル付き境界付きグラフのあいだの準同型だとする。 Tは時刻を頂点として、アトミックな時間進展（evolution, progression）を辺とするグラフ Sは状態点を頂点として、アトミックな状態遷移（遷移ステップ）を辺とする…

出口ゲート（exit gate）と出力ポート/チャネル（output port/channel）を区別して、 出口ゲートのどの点から出たかを結果（result）と呼ぶ。結果は空間的＝非時間的な概念で値＝バルクデータとして定まる。 出力ポートからのイベント列の全履歴を作用（effe…

入り口・出口の境界を持つコボルディズム的グラフの圏がほぼTQFTの域となる圏に対応するだろう。で、グラフ上のラベリングが場に対応しそう。ラベル無し（unlabelled）は自明なラベリングのこと。この圏を仮にLaGrand（labelled graphi with end-points）と…

チャネル（チャンネル） ポート {メッセージ,イベント}キュー メールボックス 共有メモリ スロット やり取りされるデータは、イベント、メッセージ、シグナルなど。

ラベル付き遷移系のラベルをコマンド／命令／アクションなどと解釈する。ラベル集合をLとして、実行系はLを辺ラベルとするグラフで表現される。一方で、プログラムコード（構文的存在物）もLを辺ラベルとするグラフで表現される。 実行系のグラフ プログラム…

と、そう言えるのではないだろうか。

「射が足し算できる」てのはけっこう難しい。可換モノイドの圏をAbMonとして、AbMon豊饒圏とするのが早いが、そのためにはAbMonにテンソル積が必要だ。ゼロ対象と双積を持てば足し算が定義できるが、逆に、足し算に何を足したら双積を作れるかがよく分からな…

なんらかの意味でオートマトンの圏があるとき、次の操作がある。 オートマトンの最小化、最適化、正規化などと呼ばれる操作 「観測可能な振る舞い」という概念があり、オートマトンにその観測可能な振る舞いを対応させる操作 指定された振る舞いを実際に行う…

色々あるなーー。 制御入り口 制御出口 初期状態 initial state 終状態 {final,termi{nal,nating}} state 始状態 start(ing) state end(ing) state 入り口ゲート entry gate 出口ゲート {exit,leave(ing)} gate 進入境界 incoming boundary 退出境界 outgoin…

遷移インスタンスは次のように書くことにする。 s|-(x, y)→s' a, bを非ブランク記号、ブランク記号を_とすると、次の分類がある。 s|-(a, b)→s' s|-(_, b)→s' s|-(a, _)→s' s|-(_, _)→s' ブランクを省略すると、 s|-(a, b)→s' s|-(, b)→s' s|-(a,)→s' s|-(,)…

ラベル概念がクセモノ。ラベルは遷移グラフの辺に付くナニカだが、 入力となる記号、データ、イベント、メッセージ 出力となる記号、データ、イベント、メッセージ 命令、アクション、コマンドの名前 その他、コンストラクタやオブザーバーの名前 おおざっぱ…

マイヒル／ネロードの定理はメイヤーオートマトンに対するものとする。 エルブランの定理 マイヒル／ネロードの定理 定数記号 コンストラクタ記号 関数記号 コマンド・メソッド記号 述語記号 クエリー・メソッド記号 基礎項 コマンド列＝状態項≒プログラムコ…

2-豊饒化（2-enrichments）とベッチ・オートマトン - 檜山正幸のキマイラ飼育記 メモ編に2-豊穣化が出てる。http://arxiv.org/abs/cs/0602077 に基づく議論。だが、これは大げさ。次で十分だろう。Mを順序モノイドとする。典型的には Lang(Σ) = Pow(Σ*) に連…

Definition 6.3.Let A = (M, A, s, ・, Ω) be a left K-linear automaton. The language accepted by A is the function ρA : A → K such that ρA(a) = Ω(a・s). オートマトンの受理言語（accepted language）を集合ではなくて線形写像（射）として捉える。 …

↓とか見ると、ベッチが何言ってるか分かる。 Title: Tree Automata and Enriched Category Theory Authors: Renato Betti, Stefano Kasangian URL: http://rendiconti.dmi.units.it/volumi/17/07.pdf Pages: 8p

あれれれっ!? James Worthingtonのオートマトンに言及してなかった。例えば、 Title: A Bialgebraic Approach to Automata and Formal Language Theory Author: James Worthington URL: http://www.math.cornell.edu/~worthing/bialgebra.pdf Kを基礎半環（…

s-(x, y)→t は遷移（のインスタンス）と言う。s∈S, t∈T でSとTが一致しなくてもよい。 遷移（のインスタンス）の集まりを遷移セット、遷移ルール、遷移関係などと言う。 s-(_, _)→t を無音遷移という。_は無音記号。 すべての遷移が無音である遷移セットを無…

参考文献： Title: A Relational Model of Non-Deterministic Dataflow Authors: Thomas T. Hildebrandt, Prakash Panangaden, Glynn Winskel URL: https://www.cl.cam.ac.uk/~gw104/journalbib.pdf Pages: 36p ↑ヒルデブラント、パナンガデン、ウィンスケル…

ゲート＝縦1セル＝2セルの横結合の対象にも、アルファベット＝横1セル＝2セルの縦結合の対象にも、モノイド積としての直和と直積の両方がある。これらの各種モノイド積に対して、対角、余対角、始対象、終対象、トレース、対合を探すことが重要。直和（足し…

時間を扱いたい（らしいね＞自分） - 檜山正幸のキマイラ飼育記 に関連して： 時間を空間に変換するのがバッファリングやアキュミュレーション（累積記憶） 空間を時間に変換するのがストリーミングやトラバースやイテレーション プログラムを時間方向に結合…

オートマトン理論に出てくるε遷移。あれは割とダメだった。形式言語理論の文脈では便利だし十分だが、プログラム意味論としてはダメダメ。次のような概念が混同されてゴッチャになった結果がε遷移。 ブランク記号＝タイムフィラー、セリンガーの言う無音{記…

×が双積の場合、 f + g := Δ;(f×g);∇ だが、双積とは別な並列同時実行 fg があるとき、 f + g := Δ;(fg);∇∃ だと思う。ここで、 Δ はの対角 ∇∃ の余対角のうちのどれかの終了を待つもの。 ∇∀ はすべてを待つもの。

基本概念は、 二重圏の簡単な例：非負行列の順序構造 非負行列の順序構造を定義する 形式言語理論のための代数 半環係数の行列 リダクトによる作用 有限有向グラフの頂点に自然数で番号を振ると、隣接行列:グラフ→自然数係数正方行列 という対応ができる。有…

遷移グラフは、局所一意な辺ラベル付き有向グラフ。辺ラベルは、重さ、色、属性、名前、電流、道のり、コストなど、なんでもよい。有向グラフの射は、決定性のグラフ射と非決定性のグラフ射の両方を導入して、オートマトンでも同じく決定性の射、非決定性の…

未整理にゴチャゴチャと書く：双オートマトン（biautomaton）という言葉は既に使われているし、その定義はまっとうなものだ。モノイドが両側から作用しているいる集合のこと。双加群＝両側加群と同じ意味での「双」。双オートマトンは、集合圏の双加群として…

決定性コンパイルのほうが分かりやすいな。 やっぱりダメみたい。QXが無限キュー（FIFO）のとき、QX*QXはQXと同値（双模倣）だが、|QX*QX|→|QX|は簡単だが、逆方向は決定性だと不自然になる。非決定性を許せば、|QX*QX|→|QX|の逆対応（転置）を取ればいいだ…

セル それは何 結合 記号 0-セル 基点 なし なし 横1-セル アルファベット 集合の直和 + 縦1-セル 集合 集合の直積 × 2セル横 オートマトン 順次結合 ; 2セル縦 オートマトン IO結合 * 3セル前後 コンパイル 連続コンパイル & 3セルに関しては、横結合;、縦…

グラフのコボルディズムに期待すること - 檜山正幸のキマイラ飼育記 メモ編 の繰り返しになるが、特に強調したい所： 並列実行と同期通信を表現できる（IO結合）。 時分割・直列化実行を定式化できる。 プログラムの実行時間とメモリ使用量を定式化できる。 …

無音{記号,遷移,アクション}またはブランク{記号,遷移,アクション}をアンダースコアで表す。入力記号Xと出力記号Yに対して、X_ = X + {_}、Y_ = Y + {_} とする。入出力記号は、X_×Y_ = X×Y + X×{_} + {_}×Y + {_}×{_} とする。アルファベットΣを、Σ=X_×Y_ …

機能的にはデグレードしている。 モードラインにIME状態が表示されない。 IMEのon/offでカーソルの色が変わらない。 CTRL+*, ESC でIMEが自動的にOFFとなったが、それもされてない。これは厳しい。 使っていたのは、 変数 w32-ime-mode-line-state-indicator…