ペラペラ（5ミリくらい）のグラフ理論の本 ICレコーダのマニュアル

双デカルト圏の余加法Δ（加法は∇）を考える。これをデータフロー計算または状態書き換え計算の文脈でどう解釈するか？ これは勘違いしやすい。僕も勘違いしていた。トレース付き双デカルトで計算処理（プロセス）をモデル化するとき、逐次計算と並列計算の違…

扱いやすい決定性オートマトンのこと。 スタートノードがひとつだけある。 ゴールノードがひとつだけある。 スタートノードとゴールノードは異なる（他の条件から出るが）。 すべてのノードはスタートノードから可達。（空集合は認識機械は除外） すべてのノ…

言語Lに関して、ξがstrong postfix (suffix) ⇔ α∈L かつ αξ ∈L となるαがある 言語Lに関して、ηがstrong prefix ⇔ α∈L かつ ηα ∈L となるαがある strong postfixの先頭文字はfollowLast集合に入る。 strong prefixの末尾文字はleadFirst集合に入る。 終状態p…

オートマトンの連接問題は「S型オートマトンとT型オートマトン」を考えるとケリが付く。Sはsubexpression、Tはtotal expressionから。S型オートマトンアルファベットA上のS型オートマトンとは、無音記号（εと同じ）を#として、A∪{#}で辺ラベル付けされた有向…

正規表現の部分式に対応するオートマトンと完全な構文単位に対応するオートマトンを区別する必要があるのだった。最初に、終状態ノードとゴールノードを区別することからはじめる。終状態はそこで終端記号が入力すると受理が成功するような状態のこと。これ…

ガードのようなディスパッチラベルのような辺ラベルと、ノードからなるグラフを考えればいい。 スキーマ属性に対応する述語ノード。台型でガードされている。真偽が、成功（通過）失敗（失格）に対応。 子オートマトンノード。objectオートマトンかarrayオー…

イプシロン辺の除去は、手間の割に効果ないのではないか。ワープ記号をちゃんとした一人前の記号としてアルファベットにいれておいて、ワープのルールを入れておけば、特に何もしなくても十分に速いような気がする。もちろん、まったく無駄なワープは削除し…

あれっ、遷移辺に貼られたディスパッチラベルが一種のガードで、どれかを選んでGOというわけで、これはコミット選択（comitted choice）になっているな。もともとが決定性なんだから、コミットもへったくれもないと言えばまーそうだ。決心をしたり運を天に任…

オートマトンを連接するとき、2種類の連接がある。 JSONの配列やオブジェクトを表すオートマトンでは、終状態から出るエンドマーカー（終端記号）の辺をそのまま残す。 正規表現を部分式から構成するときは、終状態から出るエンドマーカー（終端記号）の辺は…

バートレットのダガーについてサッパリ思い出せない。http://arxiv.org/abs/0901.3975 のPDF、p.81からp.110を急遽印刷して読むんだ！

間違っていたから。 A, B 連接 FollowLast(A)∩First(B) = 0 A, B 連接-2 ε(A)First(A)∩First(B) = 0 A | B ユニオン ε(A) = 0, ε(B) = 0, First(A)∩First(B) = 0 A? オプション ε(A) = 0 A* 繰り返し ε(A) = 0, First(A)∩FollowLast(A) = 0 First[A, B] = Fi…

なんか等式的に定義できたな。[追記]だがこれは間違っているな。明瞭性条件 訂正 - 檜山正幸のキマイラ飼育記 メモ編 に訂正がある。[/追記] A, B 連接-1 FollowLast(A)∩First(B) = 0 A, B 連接-2 ε(A)First(A)∩First(B) = 0 A | B ユニオン ε(A) = 0, ε(B) …

オートマトンMがハッキリと与えられれば、First(M), Last(M), FollowLast(M) を求めるのは簡単だ。状態点sごとに Out(s), In(s) を求めてそれを寄せ集めるに過ぎない。あとは集合の排他性の判断。 連接明瞭条件 FollowLast(M)∩First(N) = φ 合併明瞭条件 Fir…

強度ペア(τ, τ')があれば、モッジペアリングはこう定義する。 TA × TB ---------τ T(TA×B) -----------T(τ) T(T(A×B)) -----------μ T(A×B)Bを変数とすると TA × T- ---------τ T(TA×-) -----------T(τ) T(T(A×-)) -----------μ T(A×-)ドット記法を使う： T-…

bistrengthという言葉があるのは知っているが意味は知らない。bistrengthと同じかもしんない概念を考えたが、2-side strengthで両側強度と呼ぶことにする。以下に説明。C = (C, ×, 1) をモノイド圏とする。対象Aに対して、2つの関手を定義する。 A・ := λx.(…

T(A)×B → T(A×B) が余強度ってことじゃないな。やっぱり右強度と左強度が必要か。T(A×B)→T(A)×B で可換図式を全部ひっくり返したんが余強度ってことらしい。

lintの本来の意味は糸くずか。両端にノードを持たないグラフ辺をリントと言ってもいいかもしれない。2-圏のストリング図ではリントが登場する。アロー図のループは、ストリング図のリント。ループからループへの2セルは、2本のリントが出たノード。

具体的な強度付きモナドとして、計算関係では何があるか？計算（コンピューティングとソフトウェア）で出てくるモナドは、たいていコレクション系かモノイドスタンピング系。コレクション系： リストモナド + 直積 有限パワーセットモナド + 直積 スタンピン…

T = (T, μ, η) が対称モノイド圏 C = (C, ×, 1) 上のモナドで、σはCの対称だとする。さらに、τ = (τ[A] | A∈|C|) をT上のテンソル強度だとする。(T, τ) = (T, μ, η, τ) は強モナド（むしろ「強度付きモナド」がいいと思う）となる。以上の状況で、モッジのペ…

あーー、やっぱり絵算は面白い。 絵はあとで追加、今はリンク切れ状態。モッジのテンソル強度とベックの分配法則は似てるわけだけど、テンソル強度は系統的に割り当てられた分配法則（スワッパ）なのだ。Cがモノイド圏だとして、対象Aごとにスワッパ σ[A] が…

LがアルファベットA上の言語だとして、FollowLast集合が重要だ。FollowLast(L)⊆A で、次が定義。 x∈FollowLast(L) ⇔ ∃u, v∈A*.[u∈L ∧ uxv∈L]

Bruggemann-Klein & Wood の似たようなものが２つ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6882Deterministic Regular Languages (1992) （実際には1991） http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3277One-Unambi…

ホブランド（Dag Hovland）の方法は良さそうだな。 http://www.ii.uib.no/~dagh/ マーク、アンマーク方式はいらないのじゃないのかな。構文図の直接比較でもいける気がする。

http://d.hatena.ne.jp/m-hiyama/20100520/1274324275#c に書いた用語法で、ファイバー圏（fibred/fibered category）の定義を書き換えてみよう、っと。なるべく幾何学的なイメージを使うことにする。関手柱と擬射の概念を使う。後で絵を入れることにしよう…