Decidability of Innermost Termination and Context-Sensitive Termination for Semi-Constructor Term Rewriting Systems

AbstractYi and Sakai [Y. Wang and M. Sakai. Decidability of termination for semi-constructor trss, left-linear shallow trss and related systems. In the 17th International Conference on Rewriting Techniques and Applications, volume 4098 of Lecture Notes in Computer Science, pages 343–356, 2006.] showed that the termination problem is a decidable property for the class of semi-constructor term rewriting systems, which is a superclass of the class of right-ground term rewriting systems. Decidability was shown by the fact that every non-terminating TRS in the class has a loop. In this paper we modify the proof of [Y. Wang and M. Sakai. Decidability of termination for semi-constructor trss, left-linear shallow trss and related systems. In the 17th International Conference on Rewriting Techniques and Applications, volume 4098 of Lecture Notes in Computer Science, pages 343–356, 2006.] to show that both innermost termination and μ-termination are decidable properties for the class of semi-constructor TRSs