いやー、むずかしい、難しい。オートマトンを加群と考えるのは、ポリシー／指導原理としてはいいと思うが、具体的な定義では対応がつかない。双加群（両側加群）の (ax)b = a(xb) という結合律が、双オートマトン＝トランスデューサと考えるとまったく成立し…

なんか、集合圏ベースの森田の定理は出来そうな気がするな。勘違いでなければ。 集合圏が一番簡単なのではなかろうか、と思ったがそうでもない。森田理論は、どうやら本質的に多元環と加群の理論らしい。「多元環（代数）と加群」という概念がないとうまく進…

レイチェル・ブラウワー（Rachel Brouwer）の流儀（彼女がオリジナルとは違うかもしれないが）で森田の定理を解釈すると、一部（ごく一部だが）は定義からほぼ自明になる。一般化しても森田定理（Morita Theorem）のキモの部分は再現できないが、地勢を見る…

オートマトンを形式言語（列言語）の代数の上の左加群とみなす。言語の代数をAとして、a∈Aによる左作用 a・s を次のように解釈する。 s'∈(a・s) ⇔ input a may-cause transiton s-->s' 通常のオートマトンを受動的オートマトンと呼ぶ。つまり、オートマトン…

AがFLT代数だとは： 加法的ベキ等な（可換とは限らない）環である 加法から決まる順序に対してω完備である。これをω-ISRと呼ぶ。 順序に関して原子的、乗法に関して素な元の全体（atomic primes）が、ω-ISRとしての生成系になっている。 零因子を持たないこ…

森田理論では、射影生成子（progenerator）という概念が極めて重要。CがV豊饒圏だとして、Cの対象Pが射影生成子とは、 PはCの生成子（generator）である。 PはCの射影的対象（projective object）である。 Pは有限生成である。 これらは圏論（豊饒圏論だけど…

森田理論 プログラム理論 体 二値ブール代数 （可換）環 ブール代数 多元環 言語の代数 加群 オートマトン 双加群 トランスデューサー 双積 OR結合 テンソル積 並列入出力結合 加群射 オートマトン射 双加群射 トランスデューサー射

ラベルの集合がアルファベットなんじゃない。ラベル付きグラフそのものが、圏の生成系としてアルファベットなのだ。と、たったそれだけのことだが、これでモノの見方は変わった。「アルファベット→圏の生成系→圏→圏多元環」という一本道により、アルファベッ…

相変わらずマンダラ圏Mandを考えている。Mandの候補として、あるいはMandのひとつの見方として、非可換多元環上の両側加群の圏がよさそうだ。実際は、非可換半多元環上の両側半加群の圏、全部「半」が付く。 半体 半ベクトル空間 半可換環（可換半環） 半加…

"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…

有向グラフGのchildren関数 |G|→Pow(|G|) を、children(x) = {y∈|G| | xからyに向かう辺がある} で定義する。すべてのchildren(x)が全順序集合になっているようなグラフを考える。局所順序グラフと呼びたいが、誤解されそうだから、semifatグラフと呼ぶ。無…

似たことは何度も書いているような気がするが、2011年春夏シーズン向けのアルゴリズム（新作じゃないけど）。準備いろいろと記号の約束をする。 G, Hなどは有向グラフ 圏論の記法を借りて、グラフの頂点集合を|G|、辺集合を記号の乱用でGとも書く。 辺eに対…

えーと、最初に言っておくが； 複素解析ともリーマン面とも微分方程式とも特異点とも接続とも曲率とも、何の関係もない。被覆とは少し似ているし、（正錐により順序が付いた可換群としての）整係数ホモロジー群ともなんとなく関係ありそう。だが、、再帰的定…

ツリーをいちいちリアルに描くとめんどくさいから、三角形で略記。◎の「ツリー全体を表すノード」は、DOMの文書ノード（ルート要素ノードとは別）のようなもの。ルートノードとは別にあったほうが便利。参照ノードはリーフの位置にあるが、意味的には他の場…

絵だけ。説明は後で書く。別な場所に引越した。

再帰的データ型の包含性の判定、わかった - 檜山正幸のキマイラ飼育記 メモ編 の「すべてのノードをくまなくチェックしたことの確認が難しい。」というハナシ。これも大丈夫だろう。とりあえず、練習問題としてサイクルがあるツリー（言葉は変だが）のノード…

SGMLに関連して割と有名な論文。"deterministic"を使っているが、決定性オートマトンの「決定性」とは違う。 Title: Deterministic Regular Languages (1992) （実際にはたぶん1991） Authors: Bruggemann-Klein, Wood URL: http://citeseerx.ist.psu.edu/vi…

結局、分かった後から眺めれば、正規表現型のときと事情は同じだ。あからさまに（陽に）正規表現を使ってなくても、再帰的な定義を入れれば、結局は正規言語になる。「再帰的データ型（の領域）＝正規言語」と言ってよいから、正規表現型の導入と再帰的なデ…

「各レベルの構成子、演算記号」にだいたいまとめたが、別な観点からまとめておく。型の全体を代数系と考える。これは2ソート代数で、「ラベル型」ソートと「データ型」ソートを持つが、単に「ラベル」と「データ」と言ってしまうこともある。Lをラベル型の…

パリクベクトルとパリク写像の一般化としてパリク関手が定義できそうだな。Σがアルファベットとして、V = NΣ をパリク・ベクトル空間または単にパリク空間と呼ぶ。パリク空間を可換モノイドとみて、ベキ集合の半環（ブール代数係数の畳込み積の半環）をパリ…

決めた。実行が速いし簡単。推論が大変になるけど、トレードオフ。

最近またお絵描きしている。頻繁に使う絵算手法をまとめておく。まずはトレースに関するスライディング。(∇;f) をまとめてスライドしているが、こういう感じのスライディングは多い。次はアンワインディング。箱に巻き付いているワイヤーをほどくのだが、箱…

無音近傍とは、近傍の中心点からコスト0で行ける点の集合。中心点そのものが入るから、常に無音近傍は空ではない。で、今の問題は、この無音近傍の形状と標準形をどう定めるか。標準形状を決めたら、それを扱うアルゴリズムも決まる。標準形状としては、スタ…

N、Mがオートマトン、S=|N|, T=|M|は状態集合。s0, t0はスタートノード。次がアルゴリズムのステップごとの入力になる。 候補辺集合 C⊆S×T、Cは空ではない。 確定辺集合 D⊆S×T、Dは空でもよい。 調べるべき候補辺 r∈C CとDを更新してステップの結果とする。 …

妄想をたどるために使った概念や事実や定理： ブラーグマンクライン＆ウッド（Bruggemann-Klein - Wood）の1-非曖昧性（出発点） マクノートン／山田／グラシュコフの方法 Hovlandアルゴリズム（ライバルとして） ホイヘンスの原理 ダイクストラ法 ファイン…

波頭集合はステップベースじゃなくて、やっぱりコストベースのほうがいいみたいだ。ステップは、遷移グラフの辺を通るごとに1ステップと勘定する。コストは入力した（あるいは通過した）記号の数。無音遷移はステップ1でコスト0。ある点からの次の波頭集合は…

ふううううううーーーーーーーーー、ふうううううううううーーーーーーーーーーーー。正規言語の包含性判定にダイクストラ法を使うアイディアはなんとか救えそうだ、、、実に紆余曲折だったが。実行用のオートマトンと判定用のオートマトンはまったく違った…