DFD
メリット: セル形状が自由 直積の構成が極めて簡単 細分の定義が極めて簡単 台空間が多様体である必要はない(例:アフィン幾何グラフ) 近似の精度を評価できる。 目標は: 圏論的に扱いやすい〈categorically tractable〉 カスタマイズが容易〈easily cus…
n, m∈N に対して、 AL(n, m) := Mat(n, m)×Rm と定義する。ここで、 Mat(n, m)は、m行n列の行列の全体 Mat(n, m) Rm×n (a, b)∈AL(n, m), (a', b')∈AL(m, k) として、 (a, b);(a', b') := (a'a, a'b + b') と定義する。これは次の式の代入計算。 y = ax + b z…
まずは、言葉の問題。同義語らしきもの。 agent, player, voter, member, stake holder, participant alternative, candidate, (political) option, policy, social status agreement, consensus permutation, ordering, ranking rule, method, algorithm es…
何でもいいのだが、応募者(候補者)5人、審査員3人として B, D, A, E, C C, A, B, E, D D, E, C, B, A 作為的に選好が割れている。順位付け〈ranking, ordering〉が審査員を表現しているとも言えるので、順位付けのあいだの距離は審査員のあいだの距離とも…
コンドルセのステートメントを次の形にしてみる。 局所的に整合でも、大域的な不整合は起こり得る。 「局所的」の意味を2つに分ける。 セル局所的〈cell-wise locally〉 範囲局所的〈range-wise locally〉 すると: セル局所的に整合でも、大域的な不整合は…
コンドルセのパラドックスは、次の2つの意味で解釈できる。 事実としての、コンドルセ現象 コンドルセによる問題提起 いずれにしても否定的な意味はまったくない。「コンドルセ現象は事実だから、そのメカニズム/背景を解明せよ」ということになる。この意…
コンドルセのパラドックスはパラドックスではなくて、事実あるいは現象なので、コンドルセ現象と呼ぶ。コンドルセ現象の肝は: 個人が合理的なランク付けをしても、集団としてはランク付けが出来ないことがある。 集団としてのランク付けを阻害している障害…
連続 離散二値 R, C B 可換環(スカラー) ベキ等可換半環 空間S 単なる集合X 確率分布 ポッシビリティ分布 S上の状態ベクトル空間 Xのベキ集合に合併 バンドル 依存和 バンドルのセクション空間 依存積集合 連続群 モノイド 群代数 モノイドのベキ集合 群代…
ダイクストラ法(Dijkstra's algorithm)の若干抽象的な定式化として、ダイクストラ行進(Dijkstra procession)とかダイクストラ波動(Dijkstra wave)とか。いずれの場合でも、空間を過去域と現在域と未来域に分けることが出来る。現在域はウエーブフロン…
入り口・出口の境界を持つコボルディズム的グラフの圏がほぼTQFTの域となる圏に対応するだろう。で、グラフ上のラベリングが場に対応しそう。ラベル無し(unlabelled)は自明なラベリングのこと。この圏を仮にLaGrand(labelled graphi with end-points)と…
チャネル(チャンネル) ポート {メッセージ,イベント}キュー メールボックス 共有メモリ スロット やり取りされるデータは、イベント、メッセージ、シグナルなど。
ラベル付き遷移系のラベルをコマンド/命令/アクションなどと解釈する。ラベル集合をLとして、実行系はLを辺ラベルとするグラフで表現される。一方で、プログラムコード(構文的存在物)もLを辺ラベルとするグラフで表現される。 実行系のグラフ プログラム…
と、そう言えるのではないだろうか。
なんらかの意味でオートマトンの圏があるとき、次の操作がある。 オートマトンの最小化、最適化、正規化などと呼ばれる操作 「観測可能な振る舞い」という概念があり、オートマトンにその観測可能な振る舞いを対応させる操作 指定された振る舞いを実際に行う…
色々あるなーー。 制御入り口 制御出口 初期状態 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 ↑ヒルデブラント、パナンガデン、ウィンスケル…
基本概念は、 二重圏の簡単な例:非負行列の順序構造 非負行列の順序構造を定義する 形式言語理論のための代数 半環係数の行列 リダクトによる作用 有限有向グラフの頂点に自然数で番号を振ると、隣接行列:グラフ→自然数係数正方行列 という対応ができる。有…
遷移グラフは、局所一意な辺ラベル付き有向グラフ。辺ラベルは、重さ、色、属性、名前、電流、道のり、コストなど、なんでもよい。有向グラフの射は、決定性のグラフ射と非決定性のグラフ射の両方を導入して、オートマトンでも同じく決定性の射、非決定性の…
未整理にゴチャゴチャと書く:双オートマトン(biautomaton)という言葉は既に使われているし、その定義はまっとうなものだ。モノイドが両側から作用しているいる集合のこと。双加群=両側加群と同じ意味での「双」。双オートマトンは、集合圏の双加群として…
決定性コンパイルのほうが分かりやすいな。 やっぱりダメみたい。QXが無限キュー(FIFO)のとき、QX*QXはQXと同値(双模倣)だが、|QX*QX|→|QX|は簡単だが、逆方向は決定性だと不自然になる。非決定性を許せば、|QX*QX|→|QX|の逆対応(転置)を取ればいいだ…
セル それは何 結合 記号 0-セル 基点 なし なし 横1-セル アルファベット 集合の直和 + 縦1-セル 集合 集合の直積 × 2セル横 オートマトン 順次結合 ; 2セル縦 オートマトン IO結合 * 3セル前後 コンパイル 連続コンパイル & 3セルに関しては、横結合;、縦…
グラフのコボルディズムに期待すること - 檜山正幸のキマイラ飼育記 メモ編 の繰り返しになるが、特に強調したい所: 並列実行と同期通信を表現できる(IO結合)。 時分割・直列化実行を定式化できる。 プログラムの実行時間とメモリ使用量を定式化できる。 …