Almost all one-rule Thue systems have decidable word problems (Q1057265): Difference between revisions

A word \(w\in A^*\) has a border \(z\in A^*\) if there exist \(x,y\in A^*\) such that \(w=xz=zy\) and \(0<| x| <| w|\). A word is called unbordered if it has no border. It is shown that: (i) the word problem for a one-rule Thue system \(T=\{(u,v)\}\), with \(| u| >| v|\) and u unbordered, is decidable; and (ii) almost all words are unbordered. This together with the obvious decidability of the word problem for a one-rule Thue system \(T=\{(u,v)\}\) with \(| u| =| v|\) leads to the fact stated in the title of the paper.