参考文献： 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セルが中心となる。横1セルが状態遷移系を表す。 時間概念を含む。テスト付きクリーネ代数ではうまくない。 並列実行を含む。テスト付きクリーネ代数ではうまくない。 入力記号・入力言語、出力記号・出力言…

とりあえず「反距離」と呼ぶが、適切な用語とは思えない。以前は「高さ」と呼んでいた量（部分ノードセットからノードまでの距離と高さ - 檜山正幸のキマイラ飼育記 メモ編）。2つの頂点より、頂点集合と1つの頂点に関して定義するのがいいのかも。グラフGに…

有向無循環グラフGで考える。循環があるとうまくない。A⊆Node(G) とする。ノードxに対して、集合Aとxの非対称距離を次のように定義する。 {d(a, x) | a∈A } の最小値 d(a, x)は、aからxに至るパスの長さの最小値とする。dは対称ではないので距離ではない。集…

なるほど、絵の描き方の微妙な差で解釈が変わる - 檜山正幸のキマイラ飼育記 メモ編 で考えたこと。無向グラフの連結成分は、グラフの幾何的実現を考えれば純粋に位相的に定義できる。強連結成分は方向を伴うので位相だけでは定義できない。有向位相（direct…