nested word

直感的には、XMLのような構造や、callイベントやretイベントを持つトレースをイメージすると良いかと.

アルファベット $\Sigma$ 上の長さ $l$ のnested wordは組 $(w,\leadsto )$ として定義される。ここで、 $w$ は長さ $l$ の $\Sigma$ 上の語で、 $\leadsto$ は長さ $l$ のマッチング関係である。

長さ $l \geq 0$ のマッチング関係は $\{-\infty ,1,2,\ldots,l\}\times\{1,2,\ldots,l,\infty\}$ の部分集合であり、次の条件を満たす

すべてのエッジは順方向( $i\leadsto j\Rightarrow i \lt j$ )
エッジは共通のポジションを決して持たない(任意の $-\infty\lt i \lt\infty$ について $h\leadsto i$ となるような $h$ が高々一つ存在しかつ $i\leadsto j$ となるような $j$ が高々一つ存在する)
エッジは交差しない( $i\leadsto j\land i'\leadsto j'$ となるような $i\lt i'\leq j\lt j'$ を見つけることは出来ない)