An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group (Q1123272): Difference between revisions

Let T be a Thue system on the finite alphabet A. \(| A|\) stands for the cardinality of A and \(| T|\) is the size of the Thue system. If a regular Church-Rosser Thue system on A is given, an \(O(| A|^ 2\times | T|)\) algorithm is presented for computing whether the monoid \(M_ T\) presented by T is a group.