CykGraph

クラス · グラフ上の文脈自由到達可能性 (CykGraph)

struct CykGraph;

概要

辺ラベル付き有向グラフ上の文脈自由到達可能性 (CYK のグラフ版)

CNF（A->BC または A->終端）の文法を、各辺が 1 記号を表す有向グラフに適用する。各記号 $X$ について「頂点 $u$ から $v$ へ、通った辺ラベル列が $X$ から導出される歩道が存在する」頂点対 $(u, v)$ の集合を不動点反復で求める。辺は繰り返し使え、向きは固定。記号は $[0, num\_sym)$ の整数 id で表す（非終端・終端クラスを区別しない）。ビット行列（$n$ 行 $\times$ $n$ 列）の合成で $A \mathrel{|}= B \circ C$ を計算するため、 1 反復あたり $O(R n^3 / 64)$（$R$ は規則数）。

計算量

1 反復 $O(R n^3 / 64)$、最悪 $O(S R n^5 / 64)$（記号数 $S$、規則数 $R$）

構築・破棄

名前	説明	計算量
`(constructor)`	n頂点・num_sym記号の空の到達関係を構築する	$O(Sn^2/64)$

メンバ関数

名前	説明	計算量
`add`	記号 `sym` の到達対に $(u, v)$ を追加する（終端辺の登録に使う）	$O(1)$
`get`	$(u, v)$ が記号 `sym` から導出可能か	$O(1)$
`add_rule`	二項規則 `A->BC` を追加する	償却 $O(1)$
`solve`	不動点まで反復して全到達対を確定する	1反復 $O(Rn^3/64)$、最悪 $O(SRn^5/64)$

メンバ変数

名前	説明	計算量
`words`	頂点数・記号数・1 行あたりの 64 bit ワード数	$O(1)$ で参照可能
`rules`	登録済みの二項規則 `{A, B, C}`	1 規則の参照は $O(1)$
`reach`	各記号の到達可能性を表すビット行列	1 ワードの参照は $O(1)$