WEKO3
アイテム
{"_buckets": {"deposit": "1d861868-7eb4-4b23-a30b-b8c5cdf12fdd"}, "_deposit": {"id": "7649", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "7649"}, "status": "published"}, "_oai": {"id": "oai:nagoya.repo.nii.ac.jp:00007649", "sets": ["314"]}, "author_link": ["21619", "21620", "21621", "21622", "21623"], "item_1615768549627": {"attribute_name": "出版タイプ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_9_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2007-05", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "177", "bibliographicPageStart": "171", "bibliographicVolumeNumber": "1554", "bibliographic_titles": [{"bibliographic_title": "数理解析研究所講究録", "bibliographic_titleLang": "ja"}]}]}, "item_9_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "This paper shows the undecidability of confluence for length preserving string rewriting systems. It is proven by reducing the Post\u0027s correspondence problem(PCP), which is known to be undecidable, to confluence problem for length preserving string rewriting systems. More precisely, we designed a reduction algorithm having the property that the existence of a solution for a given instance of PCP concides with the non-confluence of the string rewriting system obtained from the reduction algorithm.", "subitem_description_language": "en", "subitem_description_type": "Abstract"}]}, "item_9_identifier_60": {"attribute_name": "URI", "attribute_value_mlt": [{"subitem_identifier_type": "HDL", "subitem_identifier_uri": "http://hdl.handle.net/2237/9353"}]}, "item_9_publisher_32": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "京都大学数理解析研究所", "subitem_publisher_language": "ja"}]}, "item_9_select_15": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_select_item": "publisher"}]}, "item_9_source_id_7": {"attribute_name": "ISSN(print)", "attribute_value_mlt": [{"subitem_source_identifier": "1880-2818", "subitem_source_identifier_type": "PISSN"}]}, "item_9_text_14": {"attribute_name": "フォーマット", "attribute_value_mlt": [{"subitem_text_value": "application/pdf"}]}, "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": "WANG, Yi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "21619", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "SAKAI, Masahiko", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "21620", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "NISHIDA, Naoki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "21621", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "SAKABE, Toshiki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "21622", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "KUSAKARI, Keiichirou", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "21623", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2018-02-19"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "1554_171-177.pdf", "filesize": [{"value": "348.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 348600.0, "url": {"label": "1554_171-177.pdf", "objectType": "fulltext", "url": "https://nagoya.repo.nii.ac.jp/record/7649/files/1554_171-177.pdf"}, "version_id": "4a63f0c3-ea93-451e-ab63-0773d8bf76b4"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Post\u0027s correspondence Problem", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "departmental bulletin paper", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Confluence of Length Preserving String Rewriting Systems is Undecidable", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Confluence of Length Preserving String Rewriting Systems is Undecidable", "subitem_title_language": "en"}]}, "item_type_id": "9", "owner": "1", "path": ["314"], "permalink_uri": "http://hdl.handle.net/2237/9353", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2008-01-22"}, "publish_date": "2008-01-22", "publish_status": "0", "recid": "7649", "relation": {}, "relation_version_is_last": true, "title": ["Confluence of Length Preserving String Rewriting Systems is Undecidable"], "weko_shared_id": -1}
Confluence of Length Preserving String Rewriting Systems is Undecidable
http://hdl.handle.net/2237/9353
http://hdl.handle.net/2237/9353309b3acb-8e80-4106-a346-a975707f9182
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2008-01-22 | |||||
タイトル | ||||||
タイトル | Confluence of Length Preserving String Rewriting Systems is Undecidable | |||||
言語 | en | |||||
著者 |
WANG, Yi
× WANG, Yi× SAKAI, Masahiko× NISHIDA, Naoki× SAKABE, Toshiki× KUSAKARI, Keiichirou |
|||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Post's correspondence Problem | |||||
抄録 | ||||||
内容記述 | This paper shows the undecidability of confluence for length preserving string rewriting systems. It is proven by reducing the Post's correspondence problem(PCP), which is known to be undecidable, to confluence problem for length preserving string rewriting systems. More precisely, we designed a reduction algorithm having the property that the existence of a solution for a given instance of PCP concides with the non-confluence of the string rewriting system obtained from the reduction algorithm. | |||||
言語 | en | |||||
内容記述タイプ | Abstract | |||||
出版者 | ||||||
言語 | ja | |||||
出版者 | 京都大学数理解析研究所 | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | departmental bulletin paper | |||||
出版タイプ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
ISSN(print) | ||||||
収録物識別子タイプ | PISSN | |||||
収録物識別子 | 1880-2818 | |||||
書誌情報 |
ja : 数理解析研究所講究録 巻 1554, p. 171-177, 発行日 2007-05 |
|||||
フォーマット | ||||||
application/pdf | ||||||
著者版フラグ | ||||||
値 | publisher | |||||
URI | ||||||
識別子 | http://hdl.handle.net/2237/9353 | |||||
識別子タイプ | HDL |