項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係

村田, 龍彦; MURATA, Tatsuhiko; 酒井, 正彦; SAKAI, Masahiko; 西田, 直樹; NISHIDA, Naoki; 草刈, 圭一朗; KUSAKARI, Keiichirou; 坂部, 俊樹; SAKABE, Toshiki

WEKO3

AND

lat lon distance

[[sub_check.contents]]　

[[sub_radio.contents]]

Field does not validate

[[sub_attr.contents]]　

インデックスツリー

アイテム

{"_buckets": {"deposit": "7d09a974-a8c5-41b6-ab1f-069a1655f0c6"}, "_deposit": {"id": "7651", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "7651"}, "status": "published"}, "_oai": {"id": "oai:nagoya.repo.nii.ac.jp:00007651"}, "item_9_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2005-04", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "112", "bibliographicPageStart": "106", "bibliographicVolumeNumber": "1426", "bibliographic_titles": [{"bibliographic_title": "\u4eac\u90fd\u5927\u5b66\u6570\u7406\u89e3\u6790\u7814\u7a76\u6240\u8b1b\u7a76\u9332"}]}]}, "item_9_description_4": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "\u9805\u5230\u9054\u53ef\u80fd\u6027\u554f\u984c\u3068\u306f\u3001\u4e0e\u3048\u3089\u308c\u305f2\u3064\u306e\u9805\u3068\u9805\u66f8\u63db\u3048\u7cfb(TRS) \u306b\u5bfe\u3057\u3001\u7247\u65b9\u306e\u9805(\u521d\u671f\u9805)\u304b\u3089\u3082\u3046\u7247\u65b9\u306e\u9805(\u6a19\u7684\u9805)\u3078\u5230\u9054\u3067\u304d\u308b\u304b\u3068\u3044\u3046\u554f\u984c\u3067\u3042\u308b\u3002\u3053\u306e\u554f\u984c\u306f\u4e00\u822c\u306b\u306f\u6c7a\u5b9a\u4e0d\u80fd\u3060\u304c\u3001\u6c7a\u5b9a\u53ef\u80fd\u306aTRS\u306e\u30af\u30e9\u30b9\u3082\u5b58\u5728\u3059\u308b\u3002F.Jacquemard\u306f\u3001TRS\u304c\u53f3\u7dda\u5f62\u9006\u6210\u9577\u306e\u5834\u5408\u306b\u304a\u3044\u3066\u3001\u521d\u671f\u9805\u304b\u3089\u5230\u9054\u53ef\u80fd\u306a\u5168\u3066\u306e\u9805\u3092\u53d7\u7406\u3059\u308b\u6728\u30aa\u30fc\u30c8\u30de\u30c8\u30f3(TA)\u3092\u69cb\u6210\u3057\u3001\u6a19\u7684\u9805\u304cTA\u306b\u53d7\u7406\u3055\u308c\u308b\u304b\u3067\u5230\u9054\u53ef\u80fd\u6027\u3092\u5224\u5b9a\u3059\u308b\u65b9\u6cd5\u3092\u63d0\u6848\u3057\u305f\u3002\u3055\u3089\u306b\u3001TRS\u304c\u53f3\u7dda\u5f62\u306e\u5834\u5408\u306b\u304a\u3044\u3066\u306f\u521d\u671f\u9805\u304b\u3089\u5230\u9054\u53ef\u80fd\u306a\u9805\u3092\u5168\u3066\u53d7\u7406\u3059\u308bTA\u3092\u69cb\u7bc9\u3057\u3066\u5230\u9054\u4e0d\u53ef\u80fd\u6027\u3092\u5224\u5b9a\u3059\u308b\u624b\u6cd5\u3092\u793a\u3057\u305f\u3002\u672c\u7a3f\u3067\u306f\u3001Jacquemard \u306e\u624b\u6cd5\u3092\u5143\u306b\u3057\u3066\u3001\u4efb\u610f\u306eTRS\u306b\u304a\u3044\u3066\u521d\u671f\u9805\u304b\u3089\u5230\u9054\u53ef\u80fd\u306a\u9805\u3092\u5168\u3066\u53d7\u7406\u3059\u308bTA \u3092\u3001TA\u751f\u6210\u30c4\u30fc\u30ebTimbuk\u304c\u5fc5\u305a\u51fa\u529b\u3059\u308b\u3088\u3046\u306a\u3001Timbuk\u306e\u5165\u529b\u751f\u6210\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u63d0\u6848\u3059\u308b\u3002\u307e\u305f\u3001\u63d0\u6848\u624b\u6cd5\u3068Jacquemard\u306e\u624b\u6cd5\u3092\u6bd4\u8f03\u3057\u3001TRS\u304c\u53f3\u7dda\u5f62\u306e\u5834\u5408\u306b\u304a\u3044\u3066\u306f\u5f97\u3089\u308c\u308bTA\u306e\u80fd\u529b\u304c\u7b49\u4fa1\u3067\u3042\u308b\u3053\u3068\u3092\u793a\u3059\u3001\u3055\u3089\u306b\u3001\u63d0\u6848\u3057\u305f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u6539\u826f\u3057\u8fd1\u4f3c\u7cbe\u5ea6\u306e\u5411\u4e0a\u3092\u56f3\u308b\u3002", "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/9355"}]}, "item_9_publisher_32": {"attribute_name": "\u51fa\u7248\u8005", "attribute_value_mlt": [{"subitem_publisher": "\u4eac\u90fd\u5927\u5b66\u6570\u7406\u89e3\u6790\u7814\u7a76\u6240"}]}, "item_9_relation_43": {"attribute_name": "\u7570\u7248\u3067\u3042\u308b", "attribute_value_mlt": [{"subitem_relation_type": "isVersionOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "http://hdl.handle.net/2433/47265", "subitem_relation_type_select": "URI"}}]}, "item_9_select_15": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "attribute_value_mlt": [{"subitem_select_item": "publisher"}]}, "item_9_text_14": {"attribute_name": "\u30d5\u30a9\u30fc\u30de\u30c3\u30c8", "attribute_value_mlt": [{"subitem_text_value": "application/pdf"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "\u6751\u7530, \u9f8d\u5f66"}], "nameIdentifiers": [{"nameIdentifier": "21634", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "MURATA, Tatsuhiko"}], "nameIdentifiers": [{"nameIdentifier": "21635", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "\u9152\u4e95, \u6b63\u5f66"}], "nameIdentifiers": [{"nameIdentifier": "21636", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "SAKAI, Masahiko"}], "nameIdentifiers": [{"nameIdentifier": "21637", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "\u897f\u7530, \u76f4\u6a39"}], "nameIdentifiers": [{"nameIdentifier": "21638", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "NISHIDA, Naoki"}], "nameIdentifiers": [{"nameIdentifier": "21639", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "\u8349\u5208, \u572d\u4e00\u6717"}], "nameIdentifiers": [{"nameIdentifier": "21640", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "KUSAKARI, Keiichirou"}], "nameIdentifiers": [{"nameIdentifier": "21641", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "\u5742\u90e8, \u4fca\u6a39"}], "nameIdentifiers": [{"nameIdentifier": "21642", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "SAKABE, Toshiki"}], "nameIdentifiers": [{"nameIdentifier": "21643", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "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": "1426_106-112.pdf", "filesize": [{"value": "870.7 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 870700.0, "url": {"label": "1426_106-112.pdf", "url": "https://nagoya.repo.nii.ac.jp/record/7651/files/1426_106-112.pdf"}, "version_id": "128de295-6a00-4e48-a343-81660da38571"}]}, "item_keyword": {"attribute_name": "\u30ad\u30fc\u30ef\u30fc\u30c9", "attribute_value_mlt": [{"subitem_subject": "\u6728\u30aa\u30fc\u30c8\u30de\u30c8\u30f3", "subitem_subject_scheme": "Other"}, {"subitem_subject": "\u8fd1\u4f3c", "subitem_subject_scheme": "Other"}, {"subitem_subject": "\u9805\u5230", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "jpn"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "departmental bulletin paper", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "\u9805\u5230\u9054\u53ef\u80fd\u6027\u306e\u5224\u5b9a\u306b\u304a\u3051\u308b\u6210\u9577TRS\u306b\u5bfe\u3059\u308b\u624b\u6cd5\u3068\u6b63\u898f\u5316\u898f\u5247\u306b\u3088\u308b\u624b\u6cd5\u306e\u95a2\u4fc2", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "\u9805\u5230\u9054\u53ef\u80fd\u6027\u306e\u5224\u5b9a\u306b\u304a\u3051\u308b\u6210\u9577TRS\u306b\u5bfe\u3059\u308b\u624b\u6cd5\u3068\u6b63\u898f\u5316\u898f\u5247\u306b\u3088\u308b\u624b\u6cd5\u306e\u95a2\u4fc2"}]}, "item_type_id": "9", "owner": "1", "path": ["312/313/314"], "permalink_uri": "http://hdl.handle.net/2237/9355", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_value": "2008-01-22"}, "publish_date": "2008-01-22", "publish_status": "0", "recid": "7651", "relation": {}, "relation_version_is_last": true, "title": ["\u9805\u5230\u9054\u53ef\u80fd\u6027\u306e\u5224\u5b9a\u306b\u304a\u3051\u308b\u6210\u9577TRS\u306b\u5bfe\u3059\u308b\u624b\u6cd5\u3068\u6b63\u898f\u5316\u898f\u5247\u306b\u3088\u308b\u624b\u6cd5\u306e\u95a2\u4fc2"], "weko_shared_id": 3}

項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係

http://hdl.handle.net/2237/9355

	名前 / ファイル	ライセンス	アクション
	1426_106-112.pdf (870.7 kB)

Item type

紀要論文 / Departmental Bulletin Paper(1)

公開日

2008-01-22

タイトル

項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係

著者

キーワード

主題Scheme

Other

主題

木オートマトン

キーワード

主題Scheme

Other

主題

近似

キーワード

主題Scheme

Other

主題

項到

抄録

内容記述

項到達可能性問題とは、与えられた2つの項と項書換え系(TRS) に対し、片方の項(初期項)からもう片方の項(標的項)へ到達できるかという問題である。この問題は一般には決定不能だが、決定可能なTRSのクラスも存在する。F.Jacquemardは、TRSが右線形逆成長の場合において、初期項から到達可能な全ての項を受理する木オートマトン(TA)を構成し、標的項がTAに受理されるかで到達可能性を判定する方法を提案した。さらに、TRSが右線形の場合においては初期項から到達可能な項を全て受理するTAを構築して到達不可能性を判定する手法を示した。本稿では、Jacquemard の手法を元にして、任意のTRSにおいて初期項から到達可能な項を全て受理するTA を、TA生成ツールTimbukが必ず出力するような、Timbukの入力生成アルゴリズムを提案する。また、提案手法とJacquemardの手法を比較し、TRSが右線形の場合においては得られるTAの能力が等価であることを示す、さらに、提案したアルゴリズムを改良し近似精度の向上を図る。

内容記述タイプ

Abstract

出版者

京都大学数理解析研究所

言語

jpn

資源タイプ

資源

http://purl.org/coar/resource_type/c_6501

タイプ

departmental bulletin paper

Versions

Ver.1

2021-03-01 12:17:17.334867

Show All versions

Cite as

Export

OAI-PMH

JPCOAR
DublinCore
DDI

Other Formats

JSON
BIBTEX

インデックスリンク

インデックスツリー

アイテム

項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係

× 村田, 龍彦

× MURATA, Tatsuhiko

× 酒井, 正彦

× SAKAI, Masahiko

× 西田, 直樹

× NISHIDA, Naoki

× 草刈, 圭一朗

× KUSAKARI, Keiichirou

× 坂部, 俊樹

× SAKABE, Toshiki

Versions

Share

Cite as

Export