The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dalam kertas kerja ini, kami menunjukkan bahawa penamatan dan sifat penamatan paling dalam boleh ditentukan untuk kelas sistem penulisan semula istilah (pendek kata TRS) yang kesemua pasangan kebergantungan adalah linear kanan dan cetek kanan. Kami juga menunjukkan bahawa penamatan paling dalam boleh ditentukan untuk kelas TRS yang semua pasangan kebergantungan adalah cetek. Pemerhatian utama yang biasa kepada kedua-dua kelas ini adalah seperti berikut: untuk setiap TRS dalam kelas, kita boleh membina, dengan menggunakan maklumat pasangan kebergantungan, satu set istilah terhingga supaya jika TRS tidak ditamatkan maka terdapat gelung turutan bermula dengan sebutan dalam set terhingga. Fakta ini diperoleh dengan mengubah suai analisis penyebaran hujah dalam pasangan kebergantungan cetek yang dicadangkan oleh Wang dan Sakai pada tahun 2006. Walau bagaimanapun, kami mendapat manfaat yang besar bahawa prosedur yang dihasilkan tidak memerlukan sebarang prosedur keputusan masalah kebolehcapaian yang digunakan dalam prosedur Wang untuk kes cetek, kerana kelas boleh diputuskan masalah kebolehcapaian yang diketahui tidak lebih besar daripada kelas yang dibincangkan dalam kertas ini.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Keita UCHIYAMA, Masahiko SAKAI, Toshiki SAKABE, "Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 5, pp. 953-962, May 2010, doi: 10.1587/transinf.E93.D.953.
Abstract: In this paper, we show that the termination and the innermost termination properties are decidable for the class of term rewriting systems (TRSs for short) all of whose dependency pairs are right-linear and right-shallow. We also show that the innermost termination is decidable for the class of TRSs all of whose dependency pairs are shallow. The key observation common to these two classes is as follows: for every TRS in the class, we can construct, by using the dependency-pairs information, a finite set of terms such that if the TRS is non-terminating then there is a looping sequence beginning with a term in the finite set. This fact is obtained by modifying the analysis of argument propagation in shallow dependency pairs proposed by Wang and Sakai in 2006. However we gained a great benefit that the resulted procedures do not require any decision procedure of reachability problem used in Wang's procedure for shallow case, because known decidable classes of reachability problem are not larger than classes discussing in this paper.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.953/_p
Salinan
@ARTICLE{e93-d_5_953,
author={Keita UCHIYAMA, Masahiko SAKAI, Toshiki SAKABE, },
journal={IEICE TRANSACTIONS on Information},
title={Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs},
year={2010},
volume={E93-D},
number={5},
pages={953-962},
abstract={In this paper, we show that the termination and the innermost termination properties are decidable for the class of term rewriting systems (TRSs for short) all of whose dependency pairs are right-linear and right-shallow. We also show that the innermost termination is decidable for the class of TRSs all of whose dependency pairs are shallow. The key observation common to these two classes is as follows: for every TRS in the class, we can construct, by using the dependency-pairs information, a finite set of terms such that if the TRS is non-terminating then there is a looping sequence beginning with a term in the finite set. This fact is obtained by modifying the analysis of argument propagation in shallow dependency pairs proposed by Wang and Sakai in 2006. However we gained a great benefit that the resulted procedures do not require any decision procedure of reachability problem used in Wang's procedure for shallow case, because known decidable classes of reachability problem are not larger than classes discussing in this paper.},
keywords={},
doi={10.1587/transinf.E93.D.953},
ISSN={1745-1361},
month={May},}
Salinan
TY - JOUR
TI - Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs
T2 - IEICE TRANSACTIONS on Information
SP - 953
EP - 962
AU - Keita UCHIYAMA
AU - Masahiko SAKAI
AU - Toshiki SAKABE
PY - 2010
DO - 10.1587/transinf.E93.D.953
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2010
AB - In this paper, we show that the termination and the innermost termination properties are decidable for the class of term rewriting systems (TRSs for short) all of whose dependency pairs are right-linear and right-shallow. We also show that the innermost termination is decidable for the class of TRSs all of whose dependency pairs are shallow. The key observation common to these two classes is as follows: for every TRS in the class, we can construct, by using the dependency-pairs information, a finite set of terms such that if the TRS is non-terminating then there is a looping sequence beginning with a term in the finite set. This fact is obtained by modifying the analysis of argument propagation in shallow dependency pairs proposed by Wang and Sakai in 2006. However we gained a great benefit that the resulted procedures do not require any decision procedure of reachability problem used in Wang's procedure for shallow case, because known decidable classes of reachability problem are not larger than classes discussing in this paper.
ER -