2024-03-29T10:02:14Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00019068
2023-01-16T04:08:03Z
312:313:314
Decidability of Innermost Termination and Context-Sensitive Termination for Semi-Constructor Term Rewriting Systems
Uchiyama, Keita
Sakai, Masahiko
Sakabe, Toshiki
open access
2008 Elsevier B.V. Open access under CC BY-NC-ND license.
Context-Sensitive Termination
Dependency Pair
Innermost Termination
Yi 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.
Proceedings of the 7th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2007)
Elsevier
2008-04
eng
journal article
VoR
http://hdl.handle.net/2237/21174
https://nagoya.repo.nii.ac.jp/records/19068
https://doi.org/10.1016/j.entcs.2008.03.051
1571-0661
Electronic Notes in Theoretical Computer Science
204
21
34
https://nagoya.repo.nii.ac.jp/record/19068/files/1-s2_0-S1571066108001564-main.pdf
application/pdf
355.5 kB
2018-02-21