基本的な文字列書き換え系の等価性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2013/06/16 12:56 UTC 版)
「文字列書き換え系」の記事における「基本的な文字列書き換え系の等価性」の解説
文字列書き換え系の基本的形式は項書き換え系と本質的に等価である。あるアルファベット A による文字列があり、次のような形式の部分文字列置換規則のみがあるとする。 この規則は、任意の部分文字列 x0x1...xn が y0y1...ym に置換されることを意味する。 このような文字列書き換え系は項書き換え系に再定式化することができ、そのときの置換規則は以下のようになる。 ここで、xi や yi は項書き換え系の関数シンボルである。 すなわちこの項書き換え系における文字列は、基底項である。
※この「基本的な文字列書き換え系の等価性」の解説は、「文字列書き換え系」の解説の一部です。
「基本的な文字列書き換え系の等価性」を含む「文字列書き換え系」の記事については、「文字列書き換え系」の概要を参照ください。
- 基本的な文字列書き換え系の等価性のページへのリンク