このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

ゾゾウスキ導分とゾゾウスキ共役

Brzozowskiさんの発音を調べたりしたのは、Brzozowski導分への興味が再燃したからです。

ゾゾウスキ導分(Brzozowski derivative)は形式言語理論の概念です。α、βなどが適当なアルファベット(文字の集合)の上の文字列(語)だとして、Xは文字列の集合だとします。このとき、文字列αによるXのゾゾウスキ導分 Dα(X) は次のように定義されます。

  • {β | αβ∈X}

Xに属する文字列でαを接頭辞に持つのを探して、αを取り去った残りを集めたものがゾゾウスキ導分 Dα(X) です。Dα(X) を求めるアルゴリズム擬似コードで書いてみましょう。ここで、SetとStringは変数の型宣言に使ってます。


Set R = {};
for (String ξ in X) {
if (ξ has-prefix α) {
String β = rest-of ξ omitting α;
add β to R;
}
}
return R;

導分の「導」は導関数の「導」なので、導分と微分はほぼ同義語です。実際、ゾゾウスキ導分は微分と似たような面もあるのですが、ここではそのことには言及も注目もしません。

いま注目したいのは、ゾゾウスキ導分の順序的な性質で、ガロア接続(Galois connection)と呼ばれるものです。文字列αに対して、αを接頭辞として左連接する演算を Lα (Lはleftから)とします。すると次が成立します。

  • Lα(X)⊆Y ⇔ X⊆Dα(Y)

LαとDαは一種の随伴関係にあるとも言えます。上記の ⇔ の左右の命題を書き下してみると:

  • ξ∈X ならば、αξ∈Y
  • ξ∈X ならば、ξ∈{β | αβ∈X} つまり αξ∈Y

この2つの命題は確かに同値です。

LαとDαのあいだのガロア接続による随伴関係をゾゾウスキ随伴(Brzozowski adjoint)、またはゾゾウスキ共役(Brzozowski conjugate)と呼ぶことにします。圏論の文脈だと、「随伴」が多用されるので「共役」のほうが混乱が少ないかもしれません。このゾゾウスキ共役を、形式言語理論の枠組となるトレース付き圏の対合オペレーター(involution)にまで拡張すると面白そうだと思っています。

より具体的に言うと、線形文法と(有限)オートマトンが同じであることは、トレース付き圏上のゾゾウスキ共役で説明できるはずです。具体的な行列計算ではそうなっているので、そのうち(忘れる前に)書きたいとは思っています。



[追記 date="当日"]

そのうち(忘れる前に)書きたいとは思っています。

すぐに忘れそうだから以下に一部をメモ。

トレース付き圏にいく前に、ベキ等半環の表現の話が入ったほうがたぶんスッキリするかと。ベキ等半環Rを考えるのですが、これは単なるベキ等半環じゃなくて、対合と正錐を持ちます。

  • 対合 θ:R→R は、半環の演算と整合するような θθ = id である写像
  • 正錐Pは、Rの部分半環で、Pとθ(P) でRを生成できて、P∩θ(P) = {0, 1} となるもの。

Aがベキ等可換モノイドだとすると、Aの自己準同型の集合 End(A) はベキ等半環になるので、ベキ等半環Rから End(A) への準同型は、Rの表現と考えることができます。同じことですが、AにR-半加群の構造が入るとも言えます。

Rに対合と正錐があるとき、ベキ等半環の表現 ρ:R→End(A) に対合と正錐の概念を持ち込むにはどうしたらいいでしょう? Aに正錐を持たせるのが一案ですが、それをしたくないとすると、次のような表現ρを考えるのも手かと思います。

  • a∈R が正(a∈P)のとき、x, y∈A に対して ρ(a)x≦y ⇔ x≦ρ(θ(a))

Aがベキ等可換モノイドなら、モノイド演算から順序は定義できます。その順序に関して、ρ(a)とρ(θ(a))がガロア接続を介して共役(随伴)になっているわけです。

そのようなベキ等半環Rと表現ρの例がどのようにして作られるかというと:Mが(可換とは限らない)モノイドとして、Mの2つのコピーM+とM-を準備して、単位元だけを同一した直和を作ります。これを仮に M+∨M- と書きましょう。M+とM-のあいだには自然な対応があるので、それを M+∨M- で考えれば対合になります。M+∨M- から“自由生成”した畳み込み積の半環に対して、M+∨M- の対合を半環の対合に拡張し、M+から生成された部分半環を正錐とします。

特に、モノイドMが自由モノイドであるとき、半環Rはゾゾウスキ導分を生成元として含んだ半環とみなせて、形式言語とその合併演算からなるベキ等可換モノイドAに作用します(表現または半加群構造を通して)。このときのガロア接続 ρ(a)x≦y ⇔ x≦ρ(θ(a)) がゾゾウスキ共役で与えられる、という筋書きです。

[/追記]