Semi-Thue systems with an inhibitor
A semi-Thue system with an inhibitor is one having a special symbol, called an inhibitor, that appears on the right side of every rule but does not appear on the left side of any rule. The main result of this paper is that the uniform halting problem is decidable for the class of such systems. The concept of inhibitor is related to the concept of well-behaved derivation in systems without an inhibitor. The latter concept has received some attention from those interested in the open question as to whether the uniform termination problem for one-rule semi-Thue systems is decidable.
semi-thue system uniform termination termination string rewriting well behaved derivation