Elements of finite order for finite weight-reducing and confluent Thue systems (Q1121013): Difference between revisions

Let T be a finite, weight-reducing, and confluent Thue system, and let \(M_ T\) be the monoid which it represents. The following properties are shown to be decidable in polynomial time: (1) \(M_ T\) is a group; (2) \(M_ T\) contains an idempotent element different from the identity element; (3) \(M_ T\) contains an element of finite order which is different from the identity element; (4) \(M_ T\) is a free group. Moreover, the proofs imply the following: if \(M_ T\) contains an idempotent or an element of finite order different from the identity element or an element which is not a unit then such an element can be constructed in polynomial time.