2006-09-07

そして、余代数とかは、どうでもよくなりつつあるけども、
http://d.hatena.ne.jp/m-a-o/20060906#p2
の続き。決定性有限オートマトンはある種の等式系と等価と書いたけど、非決定性の有限オートマトンや一般の有限遷移系も全く同様のことが言える。

#有限遷移系。普通の有限オートマトンは、任意の状態で、全ての入力を受け取ることができるけど、それは強すぎる仮定なので、各状態で、ありうる入力の一部しか受け取らないように限定したものを、有限遷移系と呼んでる。一般的な用語なのかどうかは知らない

この代数系はオリジナル(というほどのものではないけど)と勝手に思ってたけど、Kleene代数というものの一部になっていて、Basic Process Algebraに、単位元と0元を付け加えたものになっている。
http://en.wikipedia.org/wiki/Kleene_algebra
http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes

きちんと全部公理を書くと、



(1)x+y=y+x

(2)x+(y+z)=(x+y)+z

(3)x*(y*z)=(x*y)*z

(4)x+x=x

(5)x*(y+z)=x*y+x*z , (x+y)*z=x*z+y*z

(6)x*e = e*x = x

(7)0+x = x+0 = x

(8)0*x = x*0 = 0

(4)について、昨日書かなかったのは、必要性に気付いてなかったから。非決定性有限オートマトンでは、同じ記号列を受理する仕方が複数ありうるので、この公理が必要になる。

#(2006/09/08)
以上の公理を満たす代数系は、正しく、idempotent semiring(べき等半環)というものになっている
http://en.wikipedia.org/wiki/Semiring
うへぇ。この辺りは、殆ど同じ代数系に色んな名前が付いてて紛らわしいな。おそらく、色んな業界で異なる動機から、こうした構造が調べられてるんだろう。最近では、トロピカル代数とか、max-plus代数と呼ばれる代数系(どちらも半環)を、数学の周辺でちらほら見かけるようになりつつある。そもそも、自然数そのものが、通常の足し算と掛け算に関して、半環になっている。半環は、環に比べて不自然で扱いにくい物という印象を持ってたけど、認識を改めるべきかもしれない。ただし、今流行ってる半環の多くは、可換。

Kleene代数では、これ以外に、閉包を取る演算子が存在するけど、個人的に、これはない方が自然だと思う(末尾の追記参照)。じゃあ、Kleene閉包をどう捉えるかというと、昨日書いたように、



x = a*x + e

の解xを、aのKleene閉包と見なす。なんで、これの方が自然と感じるか。

べき等半環で、sとtの二元から自由生成されるものをFで表すとする。Fは、もうちょっと、きちんと定義すると、



(1)s,tはFの要素で、0,eとは異なる

(2)x,yがFの要素なら、x+y,x*yもFの要素

(3)以上の規則でえられるものが、Fの要素。

という感じ。要するに、sとtの二変数多項式(非可換だけど)のようなもの。そして、Fの適当な要素を、aとして、方程式x=a*x+eの解xを、Fに添加した半環をKとする。これは、三元生成の自由べき等半環Fを関係式q=a*q+eで割った半環と同型になる

#このへんの話は、離散群を、生成元と関係式で与えるとか、拡大体とかの話を知ってれば、わかりやすいと思う

生成元の有限集合Gと、関係式Rで決まるべき等半環を、Fのように書くとすると、K=Fと書ける。一方で、Fの要素の形式的無限和も許したべき等半環をF<>と書く。これは、丁度、冪級数環みたいなもの。そうすると、以下で定義される写像f:K->F<>は、半環の準同型(定義略)になる



f(s)=s

f(t)=t

f(q)=e + a + a*a + a*a*a + etc....

さて、Fは十分自然な代数と思うけど、Kleene閉包を定義することができない。F<>なら可能だけども、これは無限和を含むので、一般には(特にコンピュータ上では)扱いづらい。一方の、K=Fの方は、飽くまで有限和と、有限個の関係式のみからなるので、扱いやすい。という理由から、Kleene閉包は公理にいれず、単に方程式の解と見なすべきだと思う。

なお、この枠組みで、文脈自由文法も扱える。



A -> sAt | e

というルール(eは空の文字列)だったら、Fを考えればいい。

えーと、あと余代数というのは、結局よく分からなかったけど、分からないものに、いつまでも悩んでても仕方ない。上の枠組みは、普通の項代数と変わりない。ただ一つ、自然数やリストの場合と違うのは、あっちが、自由項代数の商を考えるのに対して、こっちは、むしろF(これも自由項代数の一種)の拡大を考えているという点にある。まあ、こんな風に概念を言い換えてみても、今のところ、取り立てて役に立つわけでもない。一つ収穫だったのは、プロセス代数理解の糸口が見えてきたことかな。大体、オートマトンにConcurrencyとInteractionとAbstraction(って何?)を追加したものが、プロセス代数らしい。よく分かってないけど

#(2006/09/09)
Kleene algebraなんかいらない、semiringで十分みたいなことを書いたけど、正規表現の「代数化」に関する問題は、結構長い歴史があって、きちんとした解決を見たのは、1990年のKozenの仕事によるらしい。また、Kleene代数を、(べき等半環のように)等式理論として特徴づけることはできないらしい。他にも色々とデリケートな問題が存在する模様。詳細は、以下の論文など
http://citeseer.csail.mit.edu/kozen90kleene.html
http://www.cs.cornell.edu/Courses/cs786/2004sp/Lectures/l07-complete.pdf

単なるべき等半環と、Kleene代数の主要な差異の一つは、Kleene代数では、aのKleene閉包が、等式e+a*x=xの最小解だということを示せる点にある。多分、もう一つ重要な点は、left-handed Kleene algebraとright-handed Kleene algebraはどちらも、Kleene algebraではないという点で、これは、FとFという二つの半環が(半環として)同型ではないということの表れかね。但し、aはFの元。

個人的には、方程式は解より本質的だという価値観に染まっているので、解を本質に置く様なKleene代数のやり方は気持ち悪いと感じる。それに、解の最小性は、実用上もあまり重要ではないと思う。実際の計算は、半環の性質のみで全部遂行できるんじゃないかと思うんだけど。まあ、あんまりこだわっても仕方ない

Wikipedia

オートマトンとべき等半環