LSLとLTL

「XMLを圏論的に」というスローガンがあったわけだ。

関係の圏Relが集合の直和を直積としてデカルト圏になるとか、エルゴットオートマトンの圏とかを横目で睨むと、XMLの圏の様相も見えてくる。

とりあえず、LSL = Linear String Languageの圏を定義しよう。Σをアルファベットして固定する。LSLの対象は任意の集合（有限に限ることもある）、X→Yの射は、BNFによる文法定義。BNFにおいて、Yの元が左辺、Xも文字が右辺に出現する。

この圏に直和でモノイド積を入れる。A+T→B+Tの形の射を新たに射としてトレースを入れる。それでトレース付きデカルト圏（双デカルト？）を作る。

同様なことを線形ツリー言語LTLに関してもやれそうだ。