有限可交换Thue系统

串重写系统（∑：R）是定义在字母表∑上的所有字符串的集合，一般情况下集合中的元素是不可刻画的。对于一个有限可交换的Thue系统（∑：R）令△R={((t1,t2,……,tn),(s1,s2,……，sn））│(a^t11a^t22……a^tnn→a^s1a^s22……a^snn)∈R}。△R是幺群N^n的一个二元关系，用△*R表示N^n上由△生成的同余，则有（∑：R）≌N^n/△*R。反之，关于N^n的任意同余θ，令∑={a1,a2,……,an}和R1={a^t11a^t22……a^tnn→a^s11a^s22……a^snn│((t1,t2,……,tn),(s1,s2,……,sn))∈θ}。记R=R1U{aiaj→ajai│i≠j,i,j=1,……，n}。则（∑：R）是有限交换的串重写系统，并且（∑：R）≌N^n/θ。

On Finite Commutative Thue System

A string-rewriting system(Σ∶R) is a set of all words or strings over some finite alphabet Σ.We know a little about the structure of the set in general.For a finite commutative Thue system(Σ∶R)，let 　　 ΔR=｛((t1，t2，…,tn),(s1,s2，…,sn))｜(at11at22…atnn→as1as22…asnn)∈R｝. ΔR is a binary on Nn， Δ*R denotes the congruence on Nn generated by Δ, then 　　 (Σ∶R)≌Nn／Δ*R. 　　Conversely,for any congruence θ on Nn，let Σ=｛a1,a2,…,an｝ and 　　 R1=｛at11at22…atnn→as11as22…asnn｜((t1，t2，…，tn)，(s1，s2,…,sn))∈θ｝. set R=R1∪｛aiaj→ajai｜i≠j,i,j=1,…,n｝.Then(Σ∶R)is a finite commutative Thue system and (Σ∶R)≌Nn／θ.