摘要
ＱＵＡＮＴＩＴＡＴＩＶＥＰＲＯＰＥＲＴＩＥＳＯＦＧＲＥＥＮＥＱＵＩＶＡＬＥＮＣＥＳＯＮＳＰＥＣＩＡＬＭＯＮＯＩＤＳＷＵＪｉｎｚｈａｏ（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＡｃａｄｅｍｉａＳｉｎｉｃａ，Ｂｅｉｊｉｎｇ１０００８０，Ｃｈｉ...
For the monoids presented by finite special Church-Rosser Thue systems,the number of each kind of Green equivalence classes is either one or infinite, and it is computable in polynomial time. As applications, the regular problem and the existence of non-trivial idempotents for such monoids are decidable in polynomial time. And a result about the descriptive power of finite special Church-Rosser Thue systems is obtained.
