Termination of Single-Threaded One-rule Semi-Thue Systems
by Wojciech Moczydlowski, Alfons Geser
This paper is a contribution to the long standing open problem of uniform termination of Semi-Thue Systems that consist of one rule s → t. McNaughton previously showed that rules incapable of
- deleting t completely from both sides
- deleting t completely from the left, and
- deleting t completely from the right, have a decidable uniform termination problem.
bibTex ref: GM05