Termination and derivational complexity of confluent one-rule string-rewriting systems

It is not known whether the termination problem is decidable for one-rule s tring-rewriting systems, though the confluence of such systems is decidable by Wrathall (in: Word Equations and Related Topics, Lecture Notes in Compu ter Science, vol. 572, 1992, pp. 237-246). In this paper we develop techniq ues to attack the termination and complexity problems of confluent one-rule string-rewriting systems. With given such a system we associate another re writing system over another alphabet. The behaviour of the two systems is c losely related and the termination problem for the new system is sometimes easier than for the original system. We apply our method to systems of the special type {a(p)b(q) --> t}, where t is an arbitrary word over {a,b}, and give a complete characterization for termination. We also give a complete analysis of the derivational complexity for the system {a(p)b(q) --> b(n)a( m)). (C) 2001 Elsevier Science B.V. All rights reserved.