Church-Rosser系统表现——么半群中正则问题的可判定性

The Decidability of Regular Problems for Monoids Presented by Church-Rosser Systems

设(T,A)是字母表A上的Church-Rosser Thue系统,M_T是它表现的么半群.M_T中元素u称为正则的,如果存在x,使得xux=u.本文证明了:M_T 中是否有一非平凡正则元是多项式时间可判定的;而对于一个任给的元素 u,u 是否是正则元却是不可判定的.

Let(A,T)be a finite Church-Rosser Thue system,M_T be the semigroup represented by(A,T),An element u in M_T is called regular,if there exists x∈M_T such as that of uxu=u.In this paper,it provesthat①it is decidable for whether or not there exists a nontrival regularelement in MT,②it is not decidable for an arbitrary given element u whether or notu is regular.