Completion of a special commutative Thue system
Zhao Xi-ying · 2001
A decision method of the completion of a finite commutative special Thue system is given. By testing Church-Rosser property of a reduced special Thue system, the completion of system can be decided. When the rule is expressed in the vector form, the overlap conditions that make Church-Rosser property hold true can be attributed to those that several properties should be satisfied by the components of rule. In so doing, an algorithm of linear time complexity is obtained finally, which is to be used to decide whether a special commutative Thue system is complete.