{"created":"2021-03-01T06:26:27.432646+00:00","id":19002,"links":{},"metadata":{"_buckets":{"deposit":"21f0bd57-c88c-492c-98ad-a0aeabcbb9c9"},"_deposit":{"id":"19002","owners":[],"pid":{"revision_id":0,"type":"depid","value":"19002"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00019002","sets":["312:313:314"]},"author_link":["55408","55409","55410","55411","55412","55413","55414","55415","55416","55417"],"item_10_alternative_title_19":{"attribute_name":"その他のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"On Decidability of Context-Sensitive Termination for Right-Linear Right-Shallow Term Rewriting Systems","subitem_alternative_title_language":"en"}]},"item_10_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2009-12","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"343","bibliographicPageEnd":"36","bibliographicPageStart":"31","bibliographicVolumeNumber":"109","bibliographic_titles":[{"bibliographic_title":"電子情報通信学会技術研究報告SS, ソフトウェアサイエンス","bibliographic_titleLang":"ja"}]}]},"item_10_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"依存対が右線形右シャローである項書換え系のクラスでは,停止性および最内停止性が決定可能であることが示されている(内山ら2008年).しかし,文脈依存停止性の決定可能性は同クラスのうち,さらに左シャローであるクラスでしか示されていない.文脈依存書換えでは依存鎖中に停止しない項が存在することが,その停止性の解析を困難にしている.本論文ではまず,内山らの決定手続きが働かない左シャローでない項書換え系を例示する.次に,この困難性をもたらす原因を取り除くための十分条件を追加し,このクラスで文脈依存停止性が決定可能となることを示す. ","subitem_description_language":"ja","subitem_description_type":"Abstract"},{"subitem_description":"It is known that termination and innermost termination are decidable for term rewriting systems (TRSs for short) whose dependency pairs are all right-linear and right-shallow (Uchiyama et al, 2008). However, decidability of context-sensitive termination requires left-shallow restriction to those TRSs. The difficulty of context-sensitive termination analysis is caused by existence of non-terminating terms in dependency chains. In this paper, we first show a left-non-shallow TRS as a counterexample against the decision procedure. Then, we give a sufficient condition to make the procedure work properly, and show that context-sensitive termination is decidable for the class.","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":"http://ci.nii.ac.jp/naid/110008001254"},{"subitem_identifier_type":"HDL","subitem_identifier_uri":"http://hdl.handle.net/2237/21106"}]},"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":"http://ci.nii.ac.jp/naid/110008001254","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":"0913-5685","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":"御宿, 義勝","creatorNameLang":"ja"}],"nameIdentifiers":[{"nameIdentifier":"55408","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"酒井, 正彦","creatorNameLang":"ja"}],"nameIdentifiers":[{"nameIdentifier":"55409","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"坂部, 俊樹","creatorNameLang":"ja"}],"nameIdentifiers":[{"nameIdentifier":"55410","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"草刈, 圭一朗","creatorNameLang":"ja"}],"nameIdentifiers":[{"nameIdentifier":"55411","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"西田, 直樹","creatorNameLang":"ja"}],"nameIdentifiers":[{"nameIdentifier":"55412","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"MISHUKU, Yoshimasa","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55413","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"SAKAI, Masahiro","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55414","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"SAKABE, Toshiki","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55415","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"KUSAKARI, Keiichirou","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55416","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"NISHIDA, Naoki","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"55417","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":"110008001254.pdf","filesize":[{"value":"949.7 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"110008001254.pdf","objectType":"fulltext","url":"https://nagoya.repo.nii.ac.jp/record/19002/files/110008001254.pdf"},"version_id":"2e3f830c-e409-47a1-9bad-519ee49a0045"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"文脈依存停止性","subitem_subject_scheme":"Other"},{"subitem_subject":"決定可能性","subitem_subject_scheme":"Other"},{"subitem_subject":"右シャロー","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"右線形右シャローな項書換え系における文脈依存停止性の決定可能性について","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"右線形右シャローな項書換え系における文脈依存停止性の決定可能性について","subitem_title_language":"ja"}]},"item_type_id":"10","owner":"1","path":["314"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2015-01-20"},"publish_date":"2015-01-20","publish_status":"0","recid":"19002","relation_version_is_last":true,"title":["右線形右シャローな項書換え系における文脈依存停止性の決定可能性について"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-16T04:07:21.082970+00:00"}