文字列書き換え系
文字列書き換え系の基本的形式は項書き換え系と本質的に等価である。あるアルファベット A による文字列があり、次のような形式の部分文字列置換規則のみがあるとする。
x 0 x 1 ⋯ x n → y 0 y 1 ⋯ y m , x i , y i ∈ A {\displaystyle x_{0}x_{1}\cdots x_{n}\rightarrow y_{0}y_{1}\cdots y_{m},\quad x_{i},y_{i}\in A}
この規則は、任意の部分文字列 x0x1...xn が y0y1...ym に置換されることを意味する。
このような文字列書き換え系は項書き換え系に再定式化することができ、そのときの置換規則は以下のようになる。
x 0 ( x 1 ( ⋯ ( x n ( x ) ) ) ⋯ ) → y 0 ( y 1 ( ⋯ ( y m ( x ) ) ⋯ ) {\displaystyle x_{0}(x_{1}(\cdots (x_{n}(x)))\cdots )\rightarrow y_{0}(y_{1}(\cdots (y_{m}(x))\cdots )}
ここで、xi や yi は項書き換え系の関数シンボルである。
すなわちこの項書き換え系における文字列は、基底項である。