Well Behaved Derivations in One-Rule Semi-Thue Systems Robert McNaughton This paper is a contribution to the investigation of theproblem, does a given one-rule semi-Thue system have an infinite derivation? It is anopen question as to whether an algorithm exists for this problem, whose complement issometimes called the uniform termination problem for one-rule semi-Thue systems. Itis well known that the corresponding problem for semi-Thue systems with finite sets ofrules is undecidable.The importance of the general problem of termination in various types ofcomputing systems is acknowledged by all. The more specific area of uniformtermination of various rewriting systems is also important, as seen in the abundantliterature, with many interesting results obtained from several points of view. In thiscategory there are three references that are most relevant to this paper: [1] points outthe importance of the uniform termination problem for certain practical computingproblems in the area of theorem proving; [2] and [7] give good accounts of varioustermination problems; [7] has a particularly useful description of the peculiarities oftermination problems for one-rule semi-Thue systems among termination problems ingeneral. The first stimulus for my own research in this area was the conferencepresentation of [7]. Two suitable general references on semi-Thue systems are [3]and [6]. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-95-15
Well Behaved Derivations in One-Rule Semi-Thue Systems
Robert McNaughton
This paper is a contribution to the investigation of theproblem, does a given one-rule semi-Thue system have an infinite derivation? It is anopen question as to whether an algorithm exists for this problem, whose complement issometimes called the uniform termination problem for one-rule semi-Thue systems. Itis well known that the corresponding problem for semi-Thue systems with finite sets ofrules is undecidable.The importance of the general problem of termination in various types ofcomputing systems is acknowledged by all. The more specific area of uniformtermination of various rewriting systems is also important, as seen in the abundantliterature, with many interesting results obtained from several points of view. In thiscategory there are three references that are most relevant to this paper: [1] points outthe importance of the uniform termination problem for certain practical computingproblems in the area of theorem proving; [2] and [7] give good accounts of varioustermination problems; [7] has a particularly useful description of the peculiarities oftermination problems for one-rule semi-Thue systems among termination problems ingeneral. The first stimulus for my own research in this area was the conferencepresentation of [7]. Two suitable general references on semi-Thue systems are [3]and [6].
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-95-15