数理解析研究所講究録
第 1915 巻 2014 年 100-112100

双対性による正規言語の Variety Theory
浦本武雄

京都大学数学教室

概要
本稿は、 理論計算機科学における一分野である 「正規–語の variety theory」を、他分野の数学者に向けて概説する目的で書かれている。 正規言語とは、 そを使うことで、 正規言語の組合せ的性質の決定可能性 (decidability) を証明する為の重要なアプローチを与える :

1. 正規言語の組合せ的性質の所属問題が有限オートマトンで解けるような言語
2. 有限モノイドの代数的性質(文字列の集合) を言い、正規表現と呼ばれる簡明な
3. 有限オートマトンの幾何的性質記法を持つことと併せて、文字列の置換やパターン検索といったプログラミングに係るテキスト処理技術 正規言語の variety theory の直接の起源は、 1965 年に広く利用される。一方、正規言語の variety theory の Sch\"utzenberger の研究にさかのぼり、 以来、 上記とは、 正規–語、 有限オートマトン、 および有限モ
ノイドの間の密接な関係性を体系化した理論として1975 年に Eilenberg によって創出されたものであり、以来今日まで、 代数学的・幾何学的論理学的方面からの幅広い研究がされて来た。 近年、 正規言語のvariety theory は、 Stone 双対性の観点から再証明再構築されつつあり、 本稿もその文脈に位置づけら
れる。

1

はじめに

一般に言語 (language) とは、有限長の語 (word) の任意の集合を言い、 中でも正規言語 (regular language)とは有限オートマトンによって受理できる言語のことを言う (\S 2)。 正規言語の組合せ的性質の研究は、理論的にも興味深いものであるのみならず、 正規表
現 (regular expression) を使ったテキスト処理技術 [6]とも関連があり、 その興味は決して理論的なものに留まらない。

特に、 本稿のテーマでもある正規言語の variety
theory は、 以下三者の間に観られる密接な関係性

三者の関係性を示唆する多くの具体的類似結果が示された [2, 14]。この三者の対応関係を、 具体例でではなくより公理的に体系化したのが、 代数的位相幾何学でも有名な S. Eilenberg であり、彼の著書 [4, 5]にまとめられている。

近年では、 正規–語の variety theory を双対定理の観点から、 より洗練された形で再証明再構築する研究が進んでおり、本稿は特にその文脈に属する。
variety theory 再構築の発端となったのは 1997 年のPippenger による研究 [10] で、それは後に Gehrke ら[7] および Rhodes ら [12] によって引き継がれた。彼
らの研究によると、 上記のうち特に上二つ :1. 正規言語の組合せ的性質
2. 有限モノイドの代数的性質の間の対応関係は、 (1’) 正規言語の成す双代数と (2’)

副有限モノイドの間の Stone 双対定理 1 の帰結として再証明できる (\S 3)。
本稿では、 残る一つのもの (3. 有限オートマトンの幾何的性質) を込めた全三者の対応関係を、 適切
1 ブール代数の成す圏と Stone 空間の成す圏の間の反辺同値

101
な双対定理の帰結として再証明し、Gehrke らによる あるという。 より形式的には、語の所属問題とは「与研究に欠けている部分を埋める。 結論から言えば、 えられた語 が、 (何らかの性質を満たす) 語から成プール代数の双代数と副有限モノイドに加え、 必要 る特定の集合 に属すか否か」 を判定する問題のこなものは副有限モノイドの表現の圏の特徴付けにあ とと言っても良い 2。
る。 より具体的に言うと、 その特徴付けとは、 副有語の集合 を一つ固定したとき 「与えられた語
限群の表現の圏であるガロア圏 (Galois category) の が に属すか否か」 を判定する問題は、 に関する
$w$

$L$

$L$

$w$

$L$

公理を弱めたものであり、 本稿はその公理を満たす

圏が常に副有限モノイドの表現の圏と同値となることを示している。
勿論、 こういった結果はあくまでも、 正規言語のvariety theory を深めるものというよりはむしろ、見通しを良くするためのものであることに注意しなけ
ればならない。 また、 見通しを良くした先に望まれるのは、 それまでは関連が明らかではなかった既存$L$

最も基本的な問題の一つであり、 $L$ の構造によってへの所属問題を決定する困難さが異なる。 正規言$L$語とは特に、 有限オートマトンと呼ばれる一種の有向グラフを使ってその所属問題が決定できる様な語の集合 (言語) を言い、 本稿の主要な関心の対象で
ある。

2.1

の知識同士を有機的につなげ、 研究の交流を生むことにある。 本稿が variety theory の専門家向けの論文というよりはむしろ、 より広く一般向けの解説記
事として書かれているのは、 その点を考慮したから$A$に他ならない。

$A^{*}$

有限オートマトンと受理言語

以下では $A$ を固定された有限集合とし、アルファベッ

ト (alphabet) と呼ぶ。 また、 $A$ 上の語 (word) とは、...
の元を有限個並べた任意の列を言い、$a_{1}a_{2}$と書いて本稿のテーマである正規言語の variety theory は、 特に
しかしながら、 本稿の分量で解説しきれるほど浅くと呼ぶ。

$\epsilon\in A^{*}$$A$$a_{n}$

上の語全体の集合を表すことにする。

を長さ

$0$

の語とし、 空語 (empty word)はない。 また、 本稿では証明には立ち入らず、 必要な箇所で参考文献を挙げるに留めている。 本稿は、 定義 1.
正規言語と有限オートマトンに関する基本的・具体 分集合的な話題から始め、 徐々に正規言語の構造を巡る抽 例えば :$A$上の言語 (language) とは、$L\subseteq A^{*}$$A^{*}$の任意の部のことを言う。

象性の高い数学に踏み入っていく様に書かれている。
$L_{1}$

2

正規可語と有限オートマトン

例えば「与えられた二進数$:=\{w\in\{0$ , 1 $\}^{*}|\Vert w\Vert_{1}\equiv 1(mod3)\}.$

はバイナリ

アルファベット $A=\{0$ , 1

$\}$

上の言語

の例となる。 ここで、 一般にアルファベット $A$ 上の$b_{0}b_{1}\cdots b_{N}$が素数であるか」 という問題には、 勿論、 それを判定するための語 $w$ と文字 $a\in A$ に対しに現れる文字$a$と書いて、 $w$ の中の個数を表す。 この例では、 例えぼ

アルゴリズムが存在する。 っまり、 決められた手順 0010111 や 0100 は(アルゴリズム) に従って処理すれば、 どんな二進数 に属さない。
砺でも素数であるか否かが機械的に分かる
また、 この言語$b_{0}b_{1}\cdots$$\Vert w\Vert_{a}$$L_{1}$に属し、 1100 や 10011 は$L_{1}$

に対する語の所属問題は勿論、決定可能であることも分かる。 実際、 と 1 から成る語 $w$ が与えられた時、 その中に現れる文字 ‘1’ の個数を数え、 それが 3 を法として 1 と合同であるか$L_{1}$ということだ。

このように語 (有限長の文字列) を入力としてその性質を判定する問題を、 語の所属問題 (membershipproblem) と言い、 その問題を判定するアルゴリズムが存在するとき、 その問題は決定可能 (decidable) で$0$2 例えば二進数の素数判定問題は勿論、「与えられた二進数が、 素数である二進数の全体から成る集合に属すか」$b_{0}b_{1}\cdots b_{N}$と単純に言い換えられる。

102を判定するアルゴリズムを書くことは決して難しくない。 しかしもう少し踏み込んで言えば、 この言語への所属問題は、 その判定に高級なアルゴリズムを使う必要はなく、 特に有限オートマトンと呼ばれる一種の有向グラフを使った簡単な方法で決定可能な例になっている。

にたどり着くとき、 $qarrow q’w$ と書く (勿論これは、定義から $q\cdot w=q’$ の時に他ならない)。例えば上のオートマトンの例で言うと:$q’$$q_{0}arrow q_{0}1101$であるし、 また :定義 2. $A$ 上の有限オートマトン (finite automaton)を言う :とは、 以下のものの 4 つ組

$q_{0}arrow q_{2}101$$\mathfrak{A}=(Q, \delta, q_{0}, F)$$\bullet$$\bullet$$\bullet$状態 (state) の有限集合$Q$;

トマトンでは、 初期状態． から出発して終状態$q0\in Q$にたどり着くのは、 語$w\in\{0, 1\}^{*}$がちょうど終状態 (final state) の集合の$L_{1}$

元であるときに他ならない。 つまり :;(2)$L_{1}=\{w\in\{0, 1\}^{*}|q_{0}arrow wq_{1}\}$$\bullet$$q_{1}$$q_{0}$

遷移関数 (transition function) $\delta:Q\cross Aarrow Q$ ;初期状態 (initial state)であることも見て取れる。 さらに言うと、 このオー

$F\subseteq Q.$となる。

以下では、 $\delta(q, a)=:q\cdot a$ と書く。 また、 語 $w\in A^{*}$
よって帰納的に $q\cdot w\in Q$ を定める。

単純に見えるこの事実の重要な点は、 この事実かへの語の所属問題を解くアルゴリズム
ら、 言語が得られるという点にある。 実際 (2) から、 語の所

通常、 有限オートマトンは、 例えば以下のような有属問題に対して、 $q\cdot\epsilon:=q$ および $q\cdot(wa):=(q\cdot w)\cdot a$ に向グラフの形式で表記することが多い。

$L_{1}$

か否か」 を判定する
から順にには、 単純にオートマトン (1) の中で$\ulcorner_{w=}a_{1}a_{2}\cdots a_{n}\in L_{1}$$\ulcorner_{q0}$で彩色された辺をたどって行って に到達するか否か」 を確かめればよいと分かり、 この手続きが「w L1 か否か」 を判定するアルゴリズム$a_{1},$ $a_{2},$$\cdots,$$q_{1}$$a_{n}$

$\in$

になる。

このように、 言語(1)$L\subseteq A^{*}$が、 何らかの有限オー

トマトン $(Q, \delta, q_{0}, F)$ の初期状態から終状態へ至る

経路上の語全体の言語と一致するとき、 への語の所属問題は決定可能であることが一般に従う。 そのようなオートマトンが存在するような言語を、 正規
醤語と言う。 形式的には :$L$

つまり、有限オートマトン $(Q, \delta, q_{0}, F)$ が与えられた
時、 $Q$ の元を頂点 (vertex) とし、二つの頂点 $q’\in Q$
に対し辺 $qarrow aq’$ があるのは、 $q’=q\cdot a$ の時とする。
$q,$

各辺は $A$ の元で彩色されていて、 各頂点 $q\in Q$ と各

文字 $a\in A$ に対して、 $qarrow aq’$ なる頂点

$q’$

がちょう

ど一つ存在する $(q’=q.a)$ 。その有向グラフの中で、とくに初期状態 $q0\in Q$ には始点のない矢印 $(arrow O)$
をつけ、 また終状態 $q\in F$ を二重丸にすることで他の状態と区別している。

$a_{1},$ $a_{2},$$\cdots,$$a_{n}$

に対して、 状態

$A$

上の言語

$L\subseteq A^{*}$

が正規言語 (regular

language) であるとは、 $A$ 上の有限オートマトン$\mathfrak{A}=(Q, \delta, q_{0}, F)$が存在して :

$L=\{w\in A^{*}|\exists q\in F. q_{0}arrow wq\}$.

(3)となるときを言う。 この時、 $L$ はオートマトン によって受理 (accept) されるという。 また、 オートマ$\mathfrak{A}$

一般に $A$ 上のオートマトン $(Q, \delta, q_{0}, F)$ と語 $w=$
$a_{1}a_{2}\cdots a_{n}\in A^{*}$

定義 3.

$q$

から順に文字で彩色された辺をたどって行って状態

トン$L(\mathfrak{A})$$\mathfrak{A}$が受理する言語 (上式の右辺) を、 以下では

と書く。

103
正規言語の形式的記法 :正規表現

2.2

正規–語が実際に活用される場面は大小さまざまある。 例えば、 単純だが典型的な事例として、「あるフォルダ以下に格納されている pdf ファイルを列挙

定義 5. $A$ 上の正規表現$p$に対し、 言語 $R(p)\subseteq A^{*}$

が以下の規則で定義される :$R(\emptyset):=\emptyset R(a):=\{a\}$$R(p+q):=R(p)\cup R(q)$$R(pq):=R(p)\cdot R(q)$$R(p\wedge q):=R(p)\cap R(q)$$R(p^{c}):=A^{*}\backslash R(p)$する」 タスクを挙げることが出来る。 実際、 このタ
スクでは、 対象フォルダ下に (もしかしたら大量に)あるファイルを一つ一つ読み込んで行き :$\bullet$

ここで、 言語 $L,$

ファイル名 ( $=$ 英数字と諸記号からなる語) がに対し、 $L\cdot R$ とは:$R\subseteq A^{*}$$L\cdot R:=\{uv\in A^{*}|u\in L\wedge v\in R\}$“.Pdf” という語で終わるか否かを判定する問題を解く必要がある。 これは勿論「pdfという語で終わる」 語の成す正規言語への所属問題

で定義される言語を表す。 また$L^{n}\cdot L$$L^{0}:=\{\epsilon\}_{\backslash }L^{n+1}:=$とするとき :に他ならない。他にも、サイズの大きいテキストファ$R(p^{*}):= \bigcup_{i=0}^{\infty}R(p)^{n}.$イルから特定の (或は複数の) キーワードを検出する

タスクなど日常的なタスクもこの種の問題を含み、正規言語への所属問題に帰着されるタスクは決して少なくない。

正規言語に特別な関心が集まるのは、 上記に加え、

正規表現

$p$

から得られる言語 $R(p)$ は、 実は常に正規言語であって、 逆に正規–語は必ずこの形で無くてはならないということが知られている [8]。

が正規である為の正規言語が正規表現という簡明な形式的記法を持つ

定理 1 (Kleene). 言語

ことにも依存している [6]。まず定義から言えば、 正

必要十分条件は、

規表現とは以下で与えられる式のことを言う 3。

$L=R(p)$ となることである。

定義 4. $A$ をアルファベットとする。 $A$ 上の正規表

この事実を背景にして、 正規言語を計算機上で実際

現 (regular expression) とは、 以下の規則で帰納的にに表現するときには、 テキスト形式で表記しやすい

定義される式のことを言う :正規表現を用いる [6]。

1. 記号
2.

$p$

$p^{c}$と$\emptyset$$q$および $A$ の各元 $a\in A$ は正規表現 ;がともに正規表現のとき、$p+q$

および

例えば、

$A$

$p^{*}$、$pq$ 、 $p\wedge q$ 、がバイナリ 7 レファベット
$y$

$\{0$

, 1 である$\}$

時、形式的な式 $(01+10)^{*}(11+00)^{*}$ や $(0(10+11)^{*})^{c}$
は $A$ 上の正規表現になる。

さらに、 正規表現$p$が与えられたとき、 帰納的に一つの言語 $R(p)$ を定義することができる。

上のある正規表現表現$p$

なければならない。 実際、例えばバイナリアルファ$\emptyset\subseteq\{0$,1$\}^{*}$には :$\emptyset = R(\emptyset)$

$=$

R((00

$+$

11)

$*\wedge$

(10

$+$

01) り

という二つの正規表現による表現がある。 表す–語としては二つの正規表現は等価だが、 重要なのは、$R((00+11)^{*}\wedge(10+01)^{*})\lrcorner$$P^{c}$が存在しては、 一般には複数ありうるという点に注意し実際に計算機で語の所属問題「w3 常この式は rextended regular expression」 と呼ばれるもので、 普通の正規表現を拡張したものだが、 後の都合上こちら
を正規表現と呼ぶことにしている。 普通の正規表現では、 $p\wedge q$とという記法は使わない。 (しかし表現できる言語は同じ。 )$p$

ここで、 正規言語 $L$ に対し $L=R(p)$ となる正規ベツト上の空言語

は正規表現．

$A$$L\subseteq A^{*}$$\in$$R(\emptyset)$」と$\ulcorner_{w}\in$を解く ときの計算量が異なるという点にある。
これはちょうど、 同じ関数でもそれを計算するプ

ログラムには複数あって、 しかも計算量に違いがあ104
るのと似ている。 そしてこのことは、 正規言語への定義 6. 言語

所属問題を効率よく解くには、 筋の良い正規表現をモノイド使う必要があることを意味している。 素朴に書き下したプログラムが (計算量などの観点から) ベストな

商モノイド

ものとは限らないのと同様、 素朴に選んだ正規表現$A^{*}$$u\equiv Lv$の syntactic monoid とは、によって割った、を以下の同値関係$L\subseteq A^{*}$$\equiv L$$A^{*}/\equiv L$$\forall x,$$\Leftrightarrow$を言う :$y\in A^{*}.(xuy\in L\Leftrightarrow xvy\in L)$.

がベストなものとは限らないのだ。 そのため、 自然

以下では言語に問題となるのは 「書き下した正規表現を (何らか$M(L)$ と書く。 また、 自然な射影を $\pi_{L}:A^{*}arrow M(L)$の基準で) 自動的に最適化できないか」 ということになるが、 正規表現の variety theory は、 この種と書く。

の問題に一定の方法論を与えてくれる。

$L\subseteq A^{*}$

が正規言語であることと、 その syntactic monoid $M(L)$ が有限モノイドであるこ

正規言語の variety theory の直接の起源は、 1965 年の Sch\"utzenberger の論文 [13] にさかのぼることが出来る。彼がその論文で示したのは、「正規言語がに対し、 その syntactic monoid を

言語の syntactic monoid の基本的な性質として、「その有限性が、 元の言語の正規性が特徴づける」 という点を挙げることが出来る [9]。
命題 1. 言語正規菖語の Variety Theory

3

$L$

$*$

を

使わない正規表現で書けること (star-free) と、 その syntactic monoid (\S 3.1) が非自明な部分群を持たないこと (aperiodic) は同値である」 という事実で、 これは正規言語の構造に関するその後の研究に大きな影響を与えた。

とは同値である。
さらに、 正規表現$p$が与えられたとき、 それが表す

正規言語 $L=R(p)$ の syntactic monoid $M(L)$ の構
造 (つまり、 その積表) は計算可能であることも知られている。

この事実と Schu\"utzenberger の定理を合わせると、 重要な決定可能性を証明することが出来る。
Sch\"utzenberger の定理は 「正規言語が を使わない正規表現で書けることと、 その syntactic monoid が非自明な部分群を持たないことは同値」 というものであったが、 それから 「与えられた正規表現 が、$*$「正規言語が、 (何らかの) 良い性質 (star-free な
ど を満たす正規表現で書けるか」 という問題は、正$)$規表現の最適化の根本にある問題で一般には解くのが難しいが、 この種の問題に対して、 Sch\"utzenbergerの結果は一つの指針を示しており、 とても強力なア
プローチとなっている。

$p$

実は

$*$

を使わない正規表現$q$と等価 (同じ言語を定める) か」が決定可能であることが従う。実際、正規が与えられた時、 その言語 $L=R(p)$ の syn-

表現

$p$

tactic monoid $M(L)$ の構造は計算可能であった

3.1
$A$

正規言語の Syntactic Monoid

を有限のアルファベットとし、なる集合とすると、$A^{*}$$A^{*}$

を $A$ 上の語からには自然にモノイド (monoid)の構造が入る 4。
syntactic monoid とは、 一般に言語$\mathring{}$その積表を見れば $M(L)$ が非自明な部分群を含むか否かが分かるため、Sch\"utzenberger の定理から、 結果
的に $L=R(p)$ がこと (つまり L
い $q$$L\subseteq A^{*}$が与えられた時、 以下で定義されるモノイドのことを

$=$

$*$

を使わない正規表現

R(q))、すなわち

$P$

が

$q$

$*$

で書ける
を含まな

と等価であること つまり $R(p)=R(q))$ も判定$($できると保証される。

言う。

3.2

正規言語の VVmiety「与えられた正規言語 が star-free であるか否か」を判定する問題は、 一見して決定困難に見える。 と$L$$\overline{4_{つまり_{}\backslash 二つの語 u,v}}\in A$

単位元となる。

の連接 $uv$ を積とし、 空語$\epsilon$が105いうのも、 「$L$が star-free でない」 と結論づけるには、 素朴には 「(無限にある)にもを「 locally testable 言語の族」や$\mathcal{V}$$\ulcorner_{piecewise}$を含まないどの正規testable 言語の族」 としても、 やはり正規言語の va-

表現でも書けない」 ことを確かめる必要がありそう

riety であることが分かる。
-free 言語の族は variety である」 とは、言い換えると-free であるという正規言語の性質は、$*$に見えるからだ。

$\ulcorner_{star}$

しかし $L$ の star-free 性を、 その (有限の大きさ$\ulcorner_{Star}$

syntactic monoid $M(L)$ の代数的性質 「非自明 上記 1 3 の閉包性を持つ」 ということだ。 Eilenbergな部分群を含まない」 で特徴づけることで、 正規言 は、 正規言語の性質 $P$ が上記の閉包性を持つ時、与語の star-free 性の決定可能性を証明することが出 えられた正規言語 がその性質 $P$ を持つか否かを、来た。 その他にも locally testability[2] や piecewise syntactic monoid $M(L)$ の代数的性質で特徴づけら
testability[14] といった、正規言語の組合せ的性質の れることを示した。
決定可能性が、 syntactic monoid を経由した同様の方法によって証明されている。
有限モノイドの Variety
このように、 正規言語の組合せ的性質は、 場合に 3.3
よってはその syntactic monoid の代数的性質で特徴 Eilenberg が示したことをより厳密に理解するには、づけられることがある。 これを利用して、 正規–語 rsyntactic monoid の代数的性質」 の意味を正確にしの$\sim$$)$$L$の組合せ的性質の決定可能性を示すというのが、

こなくてはならない。 その際に中心となるのが、 有限の方法の要になっている。 こういったアプローチをモノイドの variety という概念である。
公理的に体系化したのが Eilenberg であり、 その際
定義 8. 有限モノイドの族 が variety であるとは:に正規言語の variety という概念が導入された。
$\mathbb{V}$

定義 7. 正規言語の族が variety であるとは、 各
アルファベット $A$ に対し、 に属する上の正規言$\mathcal{V}$1.

$\mathcal{V}(A)$と書くとき :$\mathcal{V}(A)\subseteq Reg(A)$

2. 任意の$\mathcal{V}(A)$は部分ブール代数 ;$L\in \mathcal{V}(A)$$\mathbb{V}$と $w\in A^{*}$ に対し、

$w\backslash L\in$$L\in \mathcal{V}(B)$に対し、 $f^{-1}(L)\in \mathcal{V}(A)$ .
$w\backslash L$と部分モノイド $M’\leq M$ に対;$M\in \mathbb{V}$とその商 M$arrow$

M’ に対し、 $M’\in$;

3. 任意の有限個の $M_{i}\in \mathbb{V}(i=1, \cdots, n)$ に対し、$\prod_{i}M_{i}\in \mathbb{V}.$とモノイド準同型 $f:A^{*}arrow$を満たすときを言う。 ただし、$M\in \mathbb{V}$$M’\in \mathbb{V}$

2. 任意のおよび $L/w\in \mathcal{V}(A)$ ;3. 任意の$B^{*}$し、$A$$\mathcal{V}$

語全体を

1. 任意の

ただし、$\prod M_{i}$は$M_{i}$達の直積モノイドを表す。

たとえば、 raperiodic な有限モノイドの族」 は有限と $L/w$ はそれ

モノイドの variety となる。 また「全ての元が可逆なmonoid (つまり群) の族」 も有限モノイドの variety

ぞれ :

になる。
$w\backslash L := \{u\in A^{*}|wu\in L\}$有限モノイドの variety に関する最も重要な事実$L/w := \{u\in A^{*}|uw\in L\}$の一つに、「有限モノイドの variety は常に擬等式(pseudo identity) と呼ばれる一種の等式で定義できにより定義される正規言語で、 それぞれる左右からの商 (quotient) という。
例えば

$S\mathcal{F}$$L$の $w$ によを「 $star$-free 言語の族」 とすると、

る」 というものがある。 このことは例で見るのが一番分かりやすい。例えば aperiodic な有限モノイドの族$S\mathcal{F}$は上記の意味で正規言語の variety となっている。他し、$\mathbb{A}$は variety であったが、有限モノイド $M$ に対$M\in \mathbb{A}$であることと、 $M$ の全ての元 $x\in M$ が

106
以下の等式を満たすことは同値であることが知られている:を含む最小の (有限モノイドの)variety となっている
ことだ 5。

$x^{\omega}=x^{\omega+1}$.

(4)

ただし、 有限モノイド $M$ とその元 $x\in M$ に対しが与えられた時、一般に正規言語の variety$M(L)(L\in \mathcal{V})$ なる有限モノイドを含む最小の (有と書くことにする。 同限モノイドの)variety を様に、 有限モノイドの variety V が与えられたとき、$\mathcal{V}$$v\dagger$$x^{\omega}\in M$とは、$x^{n}$

なる元で idempotent であるものを表す。

上の式 (4) は擬等式の一つの例であって、上記の事
実を 「variety $A$ は擬等式$x^{\omega}=x^{\omega+1}$

で定義できる」という。簡単のため擬等式の一般的定義は Reiterman
による原論文 [11] に譲るが、 同様のことが有限モノイドの任意の variety について言える。 つまり:定理 2(Reiterman). 有限モノイドの族 が variety
であることの必要十分条件は、 それが擬等式の集合$M(L)\in \mathbb{V}$と書く。すは正規言語の variety であることが知なる正規言語るとこの時、$v\dagger$

$L$

全体の族を

$v\dagger$

られている。 Eilenberg が示したのは、 対応$\mathcal{V}\mapsto v\dagger$と $V\mapsto v\dagger$ が互いに逆の全単射となることである。

つまり :定理 3 (Eilenberg). 正規言語の variety の全体の族$\mathbb{V}$で定義可能であるときである。

を鰍、 有限-E- ノイドの variety の全体の族をると$\mathfrak{M}$とす:$\mathfrak{R}\ni \mathcal{V}\mapsto v\dagger\in \mathfrak{M}$以下では、 有限モノイドの variety V が副有限等式$\mathfrak{M}\ni V\mapsto v\dagger\in \mathfrak{R}$の集合 $E$ で定義できるとき、 $V=V(E)$ と書く。 例

えば、 (4) で述べたことから、 aperiodic なモノイドの成す variety は $V(x^{\omega}=x^{\omega+1})$

3.4と一致する。

によって、 皿と頭は同型。特に$\mathcal{V}\in \mathfrak{R}$と$V\in \mathfrak{M}$に対して :

Variety 同士の一対一対応

最後の variety(有限オートマトンの variety) に立ち入る前にまず、正規言語の variety と有限モノイドのvariety が一対一に対応していることを確認しておく$\mathcal{V} = v\dagger\dagger$(6)$\mathbb{V} = v\dagger\dagger$(7)が成り立つ。

方がいい。 その一対一対応がまさに 「正規言語の性

この結果と Reiterman の結果 (定理 2) を併せると、正であるか否か」が、規言語の variety に対し「L質が、 その syntactic monoid の性質で特徴づけられ

その syntactic monoid $M(L)$ の代数的性質によってる」 ことに相当している。

この対応を理解するにはまず、Sch\"utzenberger の定理を variety の言葉によって言い直すことが役に立つ。 Schu\"utzenberger の定理は、「正規言語 $L$ が star-$\in \mathcal{V}$$\mathcal{V}$

特徴づけられるということの意味が分かる。上で言及している様に$v\dagger$は有限モノイドの variety であるから、 Reiterman の定理により、擬等式の集合 $E$ が存

在 6 して$v\dagger=\mathbb{V}(E)$となる。 また、$\mathcal{V}=\mathcal{V}\dagger\uparrow=V(E)^{\uparrow}$free であることと、 その syntactic monoid $M(L)$ が であることと合わせると :aperiodic であることが同値」 という物であった。 こ
れを$S\mathcal{F}$と $A$ を使ってそのまま言い換えると$L\in \mathcal{V}$$\Leftrightarrow$$M(L)$ が $E$ を満たす:ということが分かる。 $M(L)$ が擬等式の集合 $E$ を満(5)たすか否かというのは、 純粋に (モノイドに関する)ということに他ならない。 さらにもう一つ注意すべ

5 そこまで白明ではな
6 存在することは知られているが、 一般にこの $E$ を具体的に特定することはとても難しい。Schutzenberger の最大の貢献は、$L\in S\mathcal{F} \Leftrightarrow M(L)\in \mathbb{A}$きことは、$\mathbb{A}$は $M(L)(L\in S\mathcal{F})$ なる有限モノイドであることを示したことであって、 これは Eilenberg の定理の系として直ちに従う訳ではない。

$S\mathcal{F}\dagger=V(x^{\omega}=x^{\omega+1})$

107
代数的性質に他ならない。 この意味で、「$L\in \mathcal{V}$か否

正規言語の variety と有限オートマトンの variety は、か」 は $M(L)$ の代数的性質によって特徴づけられる

正規言語ということだ。

ることで互いに対応していた。 同様に、 有限オート$L$に対しその syntactic monoid $M(L)$ を取

マトンの variety もこの対応関係に自然に加えることが出来る。

有限オートマトンの Variety

3.5

今、 V を有限オートマトンの variety とすると、$y$

正規言語の性質は、 その syntactic monoid の代数的に属すオートマトンによって受理される正規言語の性質と上記の意味で対応関係にあるが、 それだけではない。正規–語の性質は、 それを受理する有限オー

族 $y\ddagger_{=}\cup V(A)$ が定義できる :$V^{\ddagger}(A)$$:=\{L\subseteq A^{*}|\exists \mathfrak{A}\in V. L=L(\mathfrak{A})\}$

トマトンの幾何学的性質とも良い対応関係 [3] にあり、 有限オートマトンの variety の概念によってそするとれが公理化される。

に分かる。 一方、

定義 9. 有限オートマトンの族のときが variety であるとは、次の条件を満たすときをいう :各アルファベッ$V$

ト $A$ に対して $V(A)$ で、 V に属する $A$ 上の有限オー$y\ddagger$.

(8)は、 正規言語の variety になることが容易$\mathcal{V}$を正規言語の variety とする。 こによって 「の言語を受理する有限オー
は有限オートマト
トマトンの族」 と定義すると、$\nu\ddagger$$\mathcal{V}$$v\ddagger$

ンの variety となる。

トマトンの族を表すことにすると、定理 4. 有限オートマトンの variety 全体の族を言と

1. $V(A)$ は自明なオートマトンを含む ;すると

2. 任意のと部分オートマトン$\mathfrak{A}\in V(A)$に対し、$\mathfrak{A}’\in V(A)$3. 任意の$\mathfrak{A}\in V(A)$対し、$\mathfrak{A}’\in y(A)$4. 任意の有限個の$V(A)$ ;:$\mathfrak{A}\ni \mathcal{V}\mapsto v\ddagger\in$$\mathfrak{A}’\leq \mathfrak{A}$;害と商オートマトン$\mathfrak{A}arrow \mathfrak{A}’$に;は互いに逆の、と$\mathfrak{A}_{i}\in V(A)$に対し、$V\in \mathfrak{F}$$\mathfrak{A}$

害

(9)

(10)

$\ni V\mapsto y\ddagger\in \mathfrak{A}$と害の間の同型となる。特に$\mathcal{V}\in \mathfrak{A}$に対して :$\prod_{i}\mathfrak{A}_{i}\in$$\nu = \mathcal{V}^{\ddagger t}$$V^{\ddagger\ddagger}$$V$

5. 任意の有限個の$V(A)$$\mathfrak{A}_{i}\in V(A)$に対し、$\delta$$\mathfrak{A}\in V(B)$とモノイド準同型 $f:A^{*}arrow B^{*}$

に対し、 $f^{-1}\mathfrak{A}\in V(A)$ .
ただし、$\prod_{i}\mathfrak{A}_{i}$と$\coprod_{i}$

鶏は、 それぞれとすると、$f^{-1}\mathfrak{A}$. 成り立っ。

正規言語の性質は、 有限モノイドの性質および有限オートマトンの性質と密接に関連している。 特に正規言語の組合せ的性質を有限モノイド有限オート$\mathfrak{A}_{i}$び離散和オートマトンを表す。 また、$(Q, \delta)$

達の積およ$\mathfrak{A}\in V(B)$を

は $(Q, f^{-1}\delta)$ によって与えられる。 ここで、 $f^{-1}\delta:Q\cross Aarrow Q$ は:マトンの性質で特徴づけることで、 その決定可能性が示せる場合がある。
正規言語の variety theory は、 三つの対象 :1. 正規言語の variety$qarrow aq’ \Leftrightarrow qarrow q’f(a)(a\in A)$

2. 有限モノイドの varietyとなるように定義される。

(12)$\coprod_{i}\mathfrak{A}_{i}\in$;

6. 任意の$=$(11)

3. 有限オートマトンの variety

108
間の一対一対応という形で、 正規–D-語、 有限モノイ$\Rightarrow$

ド、 および有限オートマトンの間の関連性を体系化

現論における幾つかの概念を使って、 もう少し整理することが出来る。

し、 それにより正規言語の組合せ的性質の決定可能性を証明する、 一つの強力なアプローチを与えてく
れる。

4.1

表現関数と表現双代数

以下では $M$ を (位相) モノイド、 を体とする。一般に
$k$

$M$

4

Stone 双対性による (再) 証明

上述してきた正規言語の variety theory は、 1965 年のSch\"utzenberger の論文にさかのぼる長い歴史があるが、近年になってその再定式化再証明が進みつつあ

上の

$k$

値の表現関数 (representative function)[l]とは、 $M$ の有限次元線形表現から以下のような方法で得られる (連続) 関数を言う:

定義 10. 関数 $f$ : $Marrow k$ が表現関数 (representative

funciton) であるとは、 $M$ の有限次元線形表現

る。 その発端となったのが 1997 年の Pippenger[10]$Marrow End_{k}(V)$による研究で、 その論文では、 正規言語の variety

して、 $f=h\circ\rho$ と表せる時を言う。

theory における中心的結果の一端である、

と線形関数

$h$

$\rho$::Endk $(V)arrow k$ が存在

この定義の代わりに、 $M$ 上の表現関数とは、 $M$ の

1. 正規言語の variety

有限次元線形表現の行列成分 (matrix coeﬃcient) の和として表される関数と言っても良い。 $f:Marrow k$を上記の通りとし、 表現 の表現空間 $V$ の基底を一

2. 有限モノイドの variety$\rho$の間の一対一対応を、Stone 双対定理の系としてつ固定する。 すると、再証明する試みがなされた。 この研究は 2008 年に

表現 $\rho(s)\in End_{k}(V)$ は、 正方行列 $\rho(s)=(\rho i,j(s))$

Gehrke, Grigorieﬀ および $Pin[7]$ Rhodes およびSteinberg[12] によって引き継がれ、 その結果、 上記
二つの variety 間の対応については、 その背景がより見通し良くなった 7。

として表せる。 また $E_{i,j}\in End_{k}(V)$ を $(i, j)$ 成分のみ 1 で他は であるような行列とすれば、 結果的に、

$M$の各元 $s\in M$ の$\rho$

による$0$関数 $f$ は:$f= \sum_{i,j}h(E_{i,j})\cdot\rho_{i,j}$

結論から言えば、 正規言語の variety と有限モノという行列成分

イドの variety の間の対応は、$\rho$

1. 正規言語が成す ($\mathbb{F}_{2}$上の) 双代数 (bialgebra)

2. 有限モノイドの極限の副有限モノイド (profinite$\rho_{i,j}$の線形和で書ける。 このこととがモノイド準同型であることに注意すると、 有限個の関数$f_{(1)}^{i},$$f_{(2)}^{i}$: $Marrow k(i=1, \cdots, n)$ が存在して、 任意の $s,$ $t\in M$ に対して次が成り立つことが容易に分かる :

monoid)の間の Stone 双対性からの直接の帰結として再証明$f(s \cdot t)=\sum_{i=1}^{n}f_{(1)}^{i}(s)\cdot f_{(2)}^{i}(t)$(13)

出来る。 とくにその再証明では、「正規言語の variety
は、 2 元体$\mathbb{F}_{2}$上の双代数として特徴づけられる」 という (Rhodes と Steinberg による) 事実が鍵になる。

逆に関数 $f$ に対して、 このような等式が成り立つ
が存在するとき、 $f$ は表現関数であること$f_{(1)}^{i},$$f_{(2)}$

尤もこの事実は、 群の表現論で既に知られていた結が知られている。

果の別表現であって、 彼らによる再証明は、 群の表

さらに、 $M$ 上の$k$値表現関数の全体を $R_{k}(M)$ と7 彼らの研究において variety とは、 アルファベットを固定し置く時、 $R_{k}(M)$ には自然に双代数 (bialgebra) の構造たものを指しているが、本質的には違いはあまりない。本稿でもそれに従って、 以下では、 固定したアルファベット上の族が入る。 実際、 $f\in R_{k}(M)$ を表現関数とすると、 上$\mathcal{V}(A)$に制限したものを variety と呼ぶ。

記したように式 (13) を満たす関数$f_{(1)}^{i},$$f_{(2)}^{i}$

が存在す

109
るが、実はそれら全て表現関数となるようにとれる。 $Reg(A)$ の双代数の構造が重要になるのは、 正規言
この時、 の余積 (comultiplication) $\Delta f\in R_{k}(M)\otimes$ 語の variety を双代数 Reg (A) の部分双代数として特$f$$R_{k}(M)$

徴付けられることによる。 すなわち :を:

命題 3 (Rhodes-Steinberg). ブール部分代数$\Delta f:=\sum_{i=1}^{n}f_{(1)}^{i}\otimes f_{(2)}^{i}$$Reg(A)$ が variety であるための必要十分条件は、と定義することにより、 $R_{k}(M)$ は余代数 (coalgebra)の構造が入る。 また、 積$f\otimes g\mapsto f\cdot g\in R_{k}(M)$$\mu$$\mathcal{V}\subseteq$: $R_{k}(M)\otimes R_{k}(M)\ni$$\mathcal{V}$が双代数 Reg (A) の部分双代数となることである。

一方、 有限モノイドの成す variety も別の等価なもので置き換えることが出来る。 それは、 自由副有限は単純に :

モノイド free profinite monoid) $A*$ の商 (quotient)$($$(f\cdot g)(s):=f(s)\cdot g(s)(s\in M)$

によって定義できる。 結果的に、 この積$\mu$となる副有限モノイド $A*arrow M$ で、 これは varietyと余積内の有限モノイドの逆極限として得られる。 逆にそ$\triangle$

によって、 $R_{k}(M)$ が双代数になり、 この双代数を一

般に、 $M$ の表現双代数 (representative bialgebra) と
言う。

4.2

Rhodes と Steinberg[12] はその著書の中で、「正規言語の成すブール代数 $Reg(A)$ には、 双代数の構造が自然に入る」 ということを報告している。 実はこの$A^{*}$

上の表現双代数 $R_{F_{2}}(A^{*})$に他ならないが、重要なのは、正規言語の variety を
この双代数 $Reg(A)$ の部分双代数として特徴づけられるという点にある。

そもそも正規言語の双代数 $Reg(A)$ と表現双代数$R_{F_{2}}(A^{*})$

が同一視できるのは、 言語 $L$ が正規である

こととその特性関数の全射 (finite quotient) 全体を考えることで、 もとの variety が得られる。

4.3

正規言語のなす双代数

双代数は、 自由モノイドのような副有限モノイド $M$ から、 有限モノイドヘ

正規言語と有限モノイドの Variety

正規言語の variety と有限モノイドの variety との間の一対一対応は、 それぞれを「Reg(A) の部分双代数」

および「自由副有限モノイド $A*$ の商 (quotient)」 と取り替えることによって、Stone 双対定理の系として再証明出来る。 その最後のひとステップとして必要な事実は、 「 $Reg(A)$ の Stone 双対が $A*$ となること」 という事実である。

一般に位相モノイド $M$ に対して、 その表現双代数$R_{\mathbb{F}_{2}}(M)$はブール環になっていて、従ってブール代数でもある。 特にブール代数として$R_{\mathbb{F}_{2}}(M)$の Stone値の表: $A^{*}arrow\{O$ , 1 が現関数であることが同値になることによる。

双対を考えることが出来るが、 これは実は元のモノ

命題 2. 言語

比較的容易に分かる :$8\hat{L}$$\}$$L\subseteq A^{*}$

分条件は、 特性関数$\hat{L}$$\mathbb{F}_{2}$が正規言語である為の必要十:$A^{*}arrow \mathbb{F}_{2}$が表現関数となることである。

イド $M$ の副有限完備化になっているということが

命題 4. 位相モノイド $M$ に対し、 その表現双代数$R_{F_{2}}(M)$の Stone 双対は、 $M$ の副有限完備化 (profi-

Rhodes と Steinberg は Reg(A) 上の双代数の構造を、 nite completion)M に同型である。 特に、 $M$ が副有
正規言語の syntactic monoid を使った方法で定義し 限モノイドの時、の Stone 双対は $M$ 自身に$R_{\mathbb{F}_{2}}(M)$ているが、 それは表現双代数 $R_{F_{2}}(A^{*})$ のそれに一致同型になる。

している。 とくに正規言語の variety を考える上で$\overline{9 自由副有限モノイドと}$8 一般に集合 $X$ の部分集合 $L\subseteq X$ に対し、 その特性関数: $Xarrow\{0$ , 1 とは、 $x\in L$ に対しては 1 を、 $x\not\in L$ に対して
はを対応させる関数のことをいう。

$\hat{L}$

$\}$

$0$

の副有限完備化は、 自由モノイドで得られる副有限モノイドのこと。 また、 モノイド $M$ の副有限完備化 (profinite completion) とは、 $M$ の有限商 $Marrow H$ が成す系の逆極限のこと。
$A^{*}$

110
とくに $M=A^{*}$ と置けば、 $Reg(A)$ の Stone 双対が$\hat{A}*$となることが分かる。

この節の目標は、 有限オートマトンの variety をの表現対象にもつような圏を、 $Reg(A)$ 余加群という特定の表現に依らない形で特徴付けることにある。 実際、 それはちょうど、「正規言語の variety」$4\hat{4}*$以上の準備でようやく、正規言語の variety と有限モノイドの variety の間の一対一対応を、 Stone 双対定理を経由して再証明することが出来るようになる。 を $Reg(A)$ の双代数として特徴付けたことの、「有限Stone 双対定理は、 ブール代数の成す圏と Stone 空
間 (コンパクトハウスドルフかつ完全不連結な位

オートマトンの variety 」 の場合に相当するものと言える。

相空間) の成す圏の間の反変同値であったが、 このことと 「 $Reg(A)$ の Stone 双対は $A*$ である」 という事実から :

1. $Reg(A)$ の部分双代数$\mathcal{V}\subseteq Reg(A)$

;

ガロア圏

5.1

副有限モノイドの表現の圏ではなく副有限「群」 の表現の場合には、 そのような特徴付けが知られてい2. $A*$ の商である副有限モノイド $A*arrow M$る。 つまり、 以下のガロア圏 (Galois category) の公とが一対一に対応していることが直ちに従う。 一方、理を満たす圏は常に、 副有限群の表現の圏 (或はその Stone 双対である Hopf 代数の余加群の圏) と同

前節でこれらのそれぞれが、 正規– variety と-語の$\equiv$値となる (例えば\’i15] を参照)。 以下、 fsets と書い
有限モノイドの variety と等価であることをみたが、て有限集合と写像の圏を表す。
結果的に 1. および 2. の一対一対応は、 正規言語のvariety と有限モノイドの variety の間の一対一対応 定義 11. ガロア圏 (Galois category) とは、 圏 とを導く ということが分かる。
関手 $F:Carrow$ fsets の組 $(C, F)$ であって、 以下の公理を満たすものを言う :$C$

5は始対象 (initial object)ject) 1 を持つ ;擬ガロア圏と表現定理$C_{0})C$$\emptyset$と終対象 (finml$0$

し

正規言語の variety theory の主結果には、 (1) 正規言

語の variety と (2) 有限モノイドの variety 間の対応だけでなく、 (3) 有限オートマトンの variety との対応も含まれる。 前節では、 (1) と (2) の対応を、 (1’)$C_{1})C$つ;$C_{2})C$は有限の余直積 (coproduct) を持つ ;$C_{3})C$の任意の射 $f:Xarrow Y$ に対して、 以下の様

双代数 $Reg(A)$ の部分双代数と (2’) 自由副有限モノ
イド $A*$ の商副有限モノイドの対応から再証明できることを観たが、 ここではそれに (3) に相当するもは有限のファイバー積 (fibred product) を持な射の分解が存在する :のを加える。

$Xarrow^{f}Y$

その為に、双代数 $Reg(A)$ と副有限モノイド $A*$ がStone 双対であるという事実は、 それぞれの余加群$\searrow \nearrow^{j}$表現の成す圏の (反変) 同値性で置き換えられるとい$Z$う点に注意する。 というのも、 これらの圏は、ちょうど有限オートマトンを対象 (object) に持つ圏であって、 Reg(A)(の部分双代数) と $A*($ の商 の対応の代
わりに余加群表現の圏の反変同値性を考えること$)$

で、 同時に有限オートマトン (の成す variety) も含

めることができるからだ。

(14)

ここで

り、

$j$

$\pi$

:

: $Xarrow Z$ は strict epimorphism であ$Zarrow Y$ は単射 (monomorphism)。 また、 ある射 $i’$ : $Z’\mapsto Y$ が存在して、 $Y$ は $Z$ とZ’ の余直積 $Z\sqcup Z’$ となる;

111
$C_{4})$

任意の対象 $X\in C$ と $X$ に作用する有限群 $H$ に対して、 普遍商 (universal quotient)$X/H$ が存在し、$F_{0})F(\emptyset)=\emptyset$$\pi$$C_{3})C$の任意の射 $f:Xarrow Y$ に対して、 以下の様な射の分解が存在する :: $Xarrow$は strict epimorphism:$\pi$$Xarrow^{f}Y$および $F(1)=1$ ;(15)$\searrow^{\pi} \nearrow^{j}$$F_{1})F$はファイバー積を保つ ;

乃

$)$

$F$

は余直積を保つ ;

角

$)$

$F$

は strict epimorphisms を全射に、 単射を単$Z$

: $Xarrow Z$ は strict epimorphism であり、 $j:Z\mapsto Y$ は単射 monomorphism)

ここで

$\pi$

$($

射に移す ;$F_{0})F(\emptyset)=\emptyset$

E) $F$ はファイバー積を保つ ;$F_{4})F$

は普遍商を保つ ;$F_{5})F$は同型を反映 (reflect) する．

ガロア圏は常に副有限群の表現の圏と同値であって、また逆も然りという事実が知られている。
定理 5 (Grothendieck).

および $F(1)=1$ ;$(C, F)$をガロア圏とする。

$F_{2})F$

はプッシュアウトを保つ ;凸は strict epimorphisms を全射に、 単射を単

$)$

$F$

射に移す ;
動$)$$F$は同型を反映 (reflect) する．

このとき、 関手 $F:Carrow$ fsets の自然同型 (natural

勿論、 ガロア圏はつねに擬ガロア圏になる。 ガロアの全体 Aut(F) には、 副有限isomophism)
群の位相が自然に入り、 は副有限群 Aut(F) の表

圏の公理にあって擬ガロア圏の公理に無いものは、$F\Rightarrow F$$C$

現の圏と同値となる。

例えば普遍商に関する公理や、 単射 $Z\mapsto Y$ がある
とき $Y$ が余直積 $Y=Z$ 口 $Z’$ に分解するという公理などがある。
擬ガロア圏はもちろん、 一般には副有限群の表現

擬ガロア圏

5.2

の圏とは同値にはならないが、 代わりに副有限モノ

副有限群の表現の圏を特徴づけるガロア圏の公理は、イドの表現の圏と同値になる。 ガロア圏の場合と同それを適切に弱めることで、 ちょうど副有限モノイド

様、 その副有限モノイドは擬ガロア圏 $(C, F)$ から具の表現の圏と同値になるように出来る。 ここでは仮に、 その公理を満たす圏を擬ガロア圏 (pseudo Galois
category) とでも呼ぶことにして、 次のように定義

体的に構成できる。

する。

ノイド End (F) には自然に副有限位相が入り、定義 12. 擬ガロア圏 (pseudo Galois category) とは、
圏$C$と関手 $F:Carrow$ fsets の組 $(C, F)$ であって、 以は始対象 (initial object)$\emptyset$と終対象 (final ob-ject) 1 を持つ ;$C_{1})C$は有限のファイバー積 (fibred product) を持つ;$C_{2})C$$(C, F)$を擬ガロア圏とする。 このとき、 関

手 $F:Carrow$ fsets の自然変換 $F\Rightarrow F$ 全体がなすモ$C$

は副有限モノイド End (F) の表現の圏と同値となる。
この事実と Stone 双対定理を使うと、 (1) ブール代

数上の双代数の圏、 (2) 副有限モノイドの圏、 および下の公理を満たすものを言う :$c_{0})C$

定理 6.

は有限のプッシュアウト (pushout) を持つ ;(3) 擬ガロア圏のなす圏 10 は互いに (反変) 同値となることも示せる。 この三種の圏の間の同値性から殆ど直接の帰結として、 正規言語、 有限モノイド、 お

よび有限オートマトンの variety 間の一対一対応が示せる。
10 擬ガロア圏の間の射は、 ガロア圏の間の射 [15] と同様に定
義される。

112
参考文献
[1] Eiichi Abe. Hopf algebras. Cambridge University Press, 2004.
[2] Janusz Brzozowski and Imre Simon. Characterizations of locally testable events. Discrete
Math., pages 243-271, 1973.

[3] Laura Chaubard, Jean-Eric Pin, and Howard
Straubing. Actions, wreath products of cvarieties and concatenation product. Theoret.
Comput. Sci., pages 73-89, 2006.

[4] Samuel Eilenberg. Automata, languages andmachines. Vol. A. Academic Press, 1974.
[5] Samuel Eilenberg. Automata, languages andmachines. Vol. B. Academic Press, 1976.
[6] Jeﬀrey Friedl. Mastering Regular Expressions.
Oreilly & Associates Inc., 2006.

[7] Mai Gehrke, Serge Grigorieﬀ, and Jean-Eric
Pin. Duality and equational theory of regular
languages. In ICALP 2008, pages 246-257,
2008.

[8] Stephen Kleene. Representation of events inverve nets and finite automata. In Automata
studies, pages 3-41, 1956.
[9] Jean-Eric Pin. Varieties of formal languages.
Plenum Publishing Corp., 1986.
[10] Nicholas Pippenger. Regular languages andStone duality. Theory Comput. Syst., pages
121-134, 1997.
[11] Jan Reiterman. The birkhoﬀ theorem for finite algebras. Algebra Universalis, pages 1-10,

1982.
[12] John Rhodes and Benjamin Steinberg. The qtheory of finite semigroups. Springer-Verlag,

2008.

[13] Marcel-Paul Sch\"utzenberger.
On finitemonoids having only trivial subgroups. Infor-

mationa and Control pages 190-194, 1965.
[14] Imre Simon. Piecewise testable events. In 2nd
GI Conf., pages 214-222, 1975.
[15] Fabio Tonini. Notes on Grothendieck-Galois
theory, 2009.