# DAWG初出論文のメモ
- [The Smallest Automaton Recognizing The Subwords of a Text](https://www.sciencedirect.com/science/article/pii/0304397585901574)

## 内容

### 右同値類とDAWGの定義
- end-set(出現位置の右端の集合) に対して end-equivalentみたいな概念を作る
- 右同値類に対する補題
- 右同値類が一致しているなら片方が片方のsuffixになる
- 出現位置が一定数ズレて一致している
- 右同値類の代表元(最長要素)は以下の2つのどちらか
- prefixになっている
- $aX$, $bX$ のように, 先行する文字が2種類以上存在する
- DAWG: 右同値類に対するオートマトン
- substringを受理するオートマトンとしては最小にならない
- Fig2(a)のend-setが $\{3, 5\}$ であるノードはまとめられる
- suffixを受理するオートマトンとして見ると最小
- Myhill-Nerode theoremというのがあり, これより明らからしい
- あるオートマトンが受容する文字列集合 $L$ に対して, 文字列同士の二項関係 ${\equiv}_L$ を $x\ {\equiv}_L\ y \Leftrightarrow$ $xz$ と $yz$ のうち片方のみが $L$ に含まれるような文字列 $z$ が存在しない と定義する
- この時, 最小のオートマトンの状態数は ${\equiv}_L$ の同値類の数と一致する

### サイズ関連の証明
- end-setには包含関係があるので, それを辺として書く (Fig3(a))
- これは代表元が $X$ のノードから代表元が $YX$ のノードに辺を生やしている事になり, このグラフはSuffix Link Treeを表している
- $n > 2$ の場合, $v \leq 2n - 1$ となる
- $S$ の文字が1種類である場合, $v = n+1$
- 根がnon-branching nodeである事を仮定するための場合分け
- 代表元 $X$ に対して $aX$, $bX$ が存在する: branching node
- 代表元がprefixである場合: non-branching node
- この個数は $n$ 個以下となる
- 木の縮約を考えると, branching nodeの個数は $n-1$ 個以下
- 上界は $S={\rm ab}^k$ で達成できる
- これ以外の文字列では, $aX, bX$ が存在するような $X$ が $n-1$ 個存在しない
- $n \geq 2$ の場合, $e \leq v + n - 2$ になる
- DAWGの根付き全域木を考える
- これには $v - 1$ 個の辺が存在する
- 全域木の辺を使ってsourceから移動→全域木にない辺を1つ通る→適当なパスでsinkに移動 のようなパスを考える
- source-sink間のパスなため, suffixを表す
- パスが異なるため, 文字列も異なる
- 全域木中にすでにsource-sinkのパスが1つ存在する
- suffixは $n$ 個のため, 全域木にないパスの辺数は $n-1$ 個以下
- $n > 2$ の場合, $e$ は $3n-3$ でなく $3n-4$ で抑えられる
- ${\rm ab}^n$ が頂点数の上界を達成できる唯一の例
- この時の辺数が $2n-1$ になるため, 辺数の上界が抑えられた