2024-03-29T13:22:05Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00007550
2023-01-16T03:53:03Z
312:598:599
Decidability of Termination for Semi-Constructor TRSs, Left-Linear Shallow TRSs and Related Systems
Wang, Yi
21268
Sakai, Masahiko
21269
We consider several classes of term rewriting systems and prove that termination is decidable for these classes. By showing the cycling property of infinite dependency chains, we prove that termination is decidable for semi-constructor case, which is a superclass of right-ground TRSs. By analyzing argument propagation cycles in the dependency graph, we show that termination is also decidable for left-linear shallow TRSs. Moreover we extend these by combining these two techniques.
journal article
Springer
2006-09
application/pdf
Proceedings of 17th Int'l Conference on Term Rewriting and Applications
343
356
http://hdl.handle.net/2237/9240
https://nagoya.repo.nii.ac.jp/record/7550/files/sakai_4.pdf
eng
https://doi.org/10.1007/11805618_26
The original publication is available at www.springerlink.com.