2011-07-01から1ヶ月間の記事一覧
大域変数の参照をコモナドと考えると、大域変数への書き込みがこのコモナドのアイレンベルク/ムーアの意味での余代数となる。ということは、大域変数を読むだけのプログラムは余クライスリ圏に住んでいるので、余アイレンベルク/ムーア圏に埋め込めるから…
Yoneda(米田)は超有名だが、Morita(森田)も有名。moritableなんて概念を定義する人がいる。http://homepages.vub.ac.be/~jvercruy/EM.pdf : Defnition 3.5.1. Let T = (T ; (LA, RA); (LB, RB)) be an object in Adj(A, B). The pair (RA, RB) is said t…
higher-dimensional transition systemの関係論文を少し見ただけで、こう言うのはナンだが; 定義や定理がなんかイマイチで、役に立つ感じがしない。抽象論は大好きだが、CPU、メモリ、マシン(またはプロセス)などとの対応が鮮明じゃないと現実に適用しに…
とりとめない。並列計算を理解したい! 高次遷移系を使いたい。higher-dimensional transition systems とか higher-dimensional automata とかで検索してそれなりに引っかかる。が、なんかピンと来ない。組み合わせ幾何学の観点からは、単体的複体や方体的…
ガウスの消去法ってすごいなー。中学生でも知っている連立一次方程式の解き方なんだけど。連立一次方程式の空間は、たとえば適当なサイズの行列で表現できる。同じ解をもつ方程式を同値とするなら、定義より当然に、同値類と解が1:1に対応する。この同値関…
上下の添字を使うのはアスキーで書けない。A[i, j] とかがいいが、これだと向きがいまいちわからない。そこで、A[i->j]とかA[jΣ(B[kテンソル計算と同じ。アインシュタイン規約でΣを省略可能。Aの転置をAlloyに倣って ~A とすると、~A[ii] のように書ける。A[…
Aが有限プレ順序集合として、f:A→N が: fは全単射である。 fの像は、{1, ..., n} の形で、nはAの基数。 順序に関して単調。 このとき、fを単調シリアライゼーションと呼ぶ。次の問題を考える: 与えられたAに対して、単調シリアライゼーションはあるか? あ…
隣接行列をインシデンス行列と言うのは違うだろう。 http://en.wikipedia.org/wiki/Incidence_matrix http://en.wikipedia.org/wiki/Adjacency_matrix
グラフの頂点数と同じサイズの正方行列を計算する。頂点付値、辺付値がある。 {0, 1}半環 可達性 min-plus代数 コストの最小化(例:距離、運送費用) max-plus代数 ゲインの最大化(例:金貨拾い問題) max-times代数 乗法係数の最大化 (例:氷運搬問題) …
"Hoare algebra"って言葉は使われてないようだ。僕が使ってしまうぞ。プログラムの計算がテンソル計算と似ているのは、・→・ に対して、2つのブール半環と、それらを係数とする両側半加群が対応するからだろう。A, Bなどがプログラムで、p, qなどが条件だと…
同じ概念を次のような言い方をしている。 複行列 http://d.hatena.ne.jp/m-hiyama-memo/searchdiary?word=%CA%A3%B9%D4%CE%F3 形式テンソル http://d.hatena.ne.jp/m-hiyama-memo/searchdiary?word=%B7%C1%BC%B0%A5%C6%A5%F3%A5%BD%A5%EB テンソルグラフ htt…
僕の作業仮説であるマンダラ仮説だと、計算の世界は複雑だ。単純化しすぎた定式化はうまくいかないだろうと思っている。だが、扱いにくい複雑性ではどうにもならない。扱いやすい「単純な複雑さ」を探さなくてはならない。今知っている具体例から抽象して、…
時間も空間も何もかも離散的な状況で考える。可算無限は認めたいが、面倒なら全部有限でいい、という前提。時間発展の生成子(time evolution generator)は、正方行列Aで与えられているとする。境界(入出力)とかあるけど、とりあえずはAだけに注目。 FA(k…
ちょっと時間が余ったはずみに映画『SUPER8/スーパーエイト』を一人で見た。製作にスティーブン・スピルバーグが入っているし、監督のJ・J・エイブラムスは大のスピルバーグファンだったらしい。この映画の舞台は1979年の新興住宅街。少年たち、親子、家族…
わかりにくかったところ/困ったところ: '.' は記法としては巧妙で素晴らしい。が、その定義はサイテー。あれはないだろうよ。現状では、僕が一番気に入らないところだ。 Aが基本集合(アトムの集合)として、x:A と x:A->A の意味がわかりにくい。x:A では…
本じゃなくて言語と処理系のことだけど。書き方: 区切り記号はあんまりないようだけど、カンマで区切る(分離)ことがある。改行で区切りを認識するわけじゃない。 アトムは修飾子付きの自然数だと思えば十分のようだ。 本の説明では、アトムは大文字。 タ…
さらにチラチラ: (本じゃなくてAlloyが)全体に、オブジェクト指向言語、特にJavaと類似の構文にしようとしている印象。abstractとかextendsとか。それが良いか悪いかはともかく、やるんなら、sigじゃなくてinterfaceにすればよかったのでは。 sig(interf…
Alloy本を献本でいただいた。けど、「はじめに」しか読んでない。昨日、他もチラチラ眺めたが、チラチラではどうも分からないな。疑問を感じたところをメモしておこう。ちゃんと読めばたぶん分かるだろうから、後で読むときに「気をつける」ポイントだな。 …
hg st の -X or --exclude オプションが意外と便利。.hgignoreを書き換えないでその場で対処できる。
title: Elgot Theories: a new Perspective of Iteration Theories (Extended Abstract) authors: Jiri Adamek, Stefan Milius, Jiri Velebil URL: http://www.iti.cs.tu-bs.de/~adamek/Elgot(abstract),AMV.pdf
もともとの(かなり狭義の)フロイド/ウォーシャル法では、無向グラフ上の最短距離行列や最短経路を求める。有向グラフにして、距離を非負値コストにしてもたいして事情はかわらない。[0, ∞] に min-plusをいれた加法的ベキ等半環を係数域とする行列計算に…
計算関係だとホモロジーが使えない。アーベル圏が出てこない。アーベル圏では次が定義できる。 f : A → B ker f : Ker(f) → A coim f : A → Coim(f) = A/Ker(f) im f : Im(f) → B coker f : B → Coker(f) = B/Im(f) しかし、普通の計算(computation)の状況…
[追記] http://d.hatena.ne.jp/m-hiyama-memo/20110713/1310515189 とだぶっていた。[/追記]もともとの(かなり狭義の)フロイド/ウォーシャル法では、無向グラフ上の最短距離行列や最短経路を求める。有向グラフにして、距離を非負値コストにしてもたいし…
文字「L」自体には特に意味が無い。プレースホルダーつうか変数つうか。適当な有限個の代数(広い意味の「代数」!)の集合上を走る変数がL。代数系の集合は {I, F1, F2, N, Z} あたりか。 I または I -- 自明なモノイド F1 または F1 -- 自明な零付きモノイ…
初歩的圏という言葉が例えば次に出てくる。 古典計算と量子計算 - 檜山正幸のキマイラ飼育記 メモ編 ブレイドやタングルの表現とマルコフ・トレース - 檜山正幸のキマイラ飼育記 メモ編 初歩的分断亜群 - 檜山正幸のキマイラ飼育記 メモ編 初歩的圏(rudimen…
ええーっ、ヤコビ図(Jacobi diagram)って、ファインマン図(Feynman diagram)と同じなの。web diagramなんて(もう使われることはなさそうな)名前もあるんだ。
http://funinf.cs.unibuc.ro/~gheorghe/ がリンク切れになっている。 今生きているURLは: http://www.cs.uiuc.edu/homes/stefanes/mirrorNus/ http://picasaweb.google.com/elETcris/CMR2007
僕がプログラム意味論とTQFTが関係すると思い出したのは、マーク・ホプキンスの観測と示唆がキッカケだ。マークの観測は完全に正しかった。ステファネスクがやっていたことはそれを裏付けるし、最近のシャイ・ハランのF1の研究(Non-Additive geometry) は…
ライデマイスター移動の番号イチ、ニ、サンが覚えられなくてずっと困っている。ヤン・バクスター関係式とか名前が付いていればわかるのだが、番号は一番苦手だ。ところがだ、この図を見ていて気がついた。射影図の交差点が上から順に1個、2個、3個なのだ。そ…
マルコフ移動についてはココとかに書いているが、絵がなかった。絵はこうなる。 「マルコフ」で検索