The Church-Rosser property and special Thue systems (Q1071759): Difference between revisions

In an earlier paper [ibid. 35, 109-114 (1985; Zbl 0563.03018)] we gave an \(O(| T|^ 3)\) algorithm for testing the Church-Rosser property of Thue systems, where \(| T|\) is the total size of the Thue system. Here we improve that bound to O(k\(| T|)\), where k is the number of rules in T, in the case when the Thue system is special, i.e., when all its rules are of the form (x,\(\lambda)\) where \(\lambda\) is the empty string. Also obtained are several results on special Thue systems which may be of independent interest.