{"created":"2021-03-01T06:26:30.751783+00:00","id":19053,"links":{},"metadata":{"_buckets":{"deposit":"7e269811-5262-4d17-9eb4-cdd778a07bb9"},"_deposit":{"id":"19053","owners":[],"pid":{"revision_id":0,"type":"depid","value":"19053"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00019053","sets":["312:313:314"]},"author_link":["55635","55636","55637"],"item_10_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2010-05","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"962","bibliographicPageStart":"953","bibliographicVolumeNumber":"E93D","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on information and systems","bibliographic_titleLang":"en"}]}]},"item_10_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_10_identifier_60":{"attribute_name":"URI","attribute_value_mlt":[{"subitem_identifier_type":"URI","subitem_identifier_uri":"https://search.ieice.org/"},{"subitem_identifier_type":"HDL","subitem_identifier_uri":"http://hdl.handle.net/2237/21159"}]},"item_10_publisher_32":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"一般社団法人電子情報通信学会","subitem_publisher_language":"ja"}]},"item_10_relation_43":{"attribute_name":"関連情報","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_10_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"(c)一般社団法人電子情報通信学会。本文データは学協会の許諾に基づきCiNiiから複製したものである","subitem_rights_language":"ja"}]},"item_10_select_15":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_10_source_id_7":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0916-8532","subitem_source_identifier_type":"PISSN"}]},"item_1615787544753":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"UCHIYAMA, Keita","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55635","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"SAKAI, Masahiko","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55636","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"SAKABE, Toshiki","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55637","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-02-21"}],"displaytype":"detail","filename":"e93-d_5_953.pdf","filesize":[{"value":"505.8 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"e93-d_5_953.pdf","objectType":"fulltext","url":"https://nagoya.repo.nii.ac.jp/record/19053/files/e93-d_5_953.pdf"},"version_id":"a091b25b-2c6d-49db-9364-f278a6117983"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"looping sequence","subitem_subject_scheme":"Other"},{"subitem_subject":"argument propagation","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs","subitem_title_language":"en"}]},"item_type_id":"10","owner":"1","path":["314"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2015-01-29"},"publish_date":"2015-01-29","publish_status":"0","recid":"19053","relation_version_is_last":true,"title":["Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-16T04:08:01.059671+00:00"}