{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00195823","sets":["934:935:9619:9764"]},"path":["9764"],"owner":"44499","recid":"195823","title":["木から文字列への決定性降下型変換器の早期化"],"pubdate":{"attribute_name":"公開日","attribute_value":"2019-05-21"},"_buckets":{"deposit":"c9c2a977-bb76-45e3-8a9a-c1812a95bd67"},"_deposit":{"id":"195823","pid":{"type":"depid","value":"195823","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"木から文字列への決定性降下型変換器の早期化","author_link":["467678","467677","467679","467676"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"木から文字列への決定性降下型変換器の早期化"},{"subitem_title":"Earliest form on Deterministic Top-down Tree-to-string Transducers","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[発表概要，Unrefereed Presentation Abstract] ","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2019-05-21","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻"},{"subitem_text_value":"東北大学電気通信研究所"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Informatics and Engineering, The University of Electro-Communications","subitem_text_language":"en"},{"subitem_text_value":"Research Institute of Electrical Communication, Tohoku University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/195823/files/IPSJ-TPRO1202009.pdf","label":"IPSJ-TPRO1202009.pdf"},"date":[{"dateType":"Available","dateValue":"2021-05-21"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1202009.pdf","filesize":[{"value":"100.6 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"f0f9b2a9-d6bc-48c3-8a7a-ceaa88e73774","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2019 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"高橋, 祐多"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"中野, 圭介"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yuta, Takahashi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Keisuke, Nakano","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"木から文字列への決定性降下型変換器（deterministic top-down tree-to-string transducers，yDTs）は，木構造データを入力とし，文字列を出力するような関数を扱うモデルの1つである．与えられた2つのyDTが，あらゆる同じ入力に対して同じ出力をするかという等価性判定は，決定可能であることが知られている．既存の等価性判定アルゴリズムは，2つの半アルゴリズムを組み合わせることで等価性判定を行っているため，計算量の見積りが不可能である．一方，yDTが線型の場合，正規形を求めることでたかだか指数時間で決定できることが知られている．そのアルゴリズムでは，言語の最大共通接頭辞・接尾辞や周期性を利用することで早期化を行った後，最小化することで正規形を求め，等価性判定を行っている．そこで，計算量を見積もることができるyDTの等価性判定アルゴリズムの実現に向け，本発表では線型yDTの等価性判定アルゴリズムにおいて用いられる早期化を非線型yDTに対して適用できるよう一般化する．具体的には，yDTに対して正規先読みを追加することで，早期に出力可能な文字列を可能な限り早く出力する正規先読み付きyDTを構築する．","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A deterministic top-down tree-to-string transducer (yDT) is a model of functions which transform tree-structured data to a string. It is known that the equivalence problem on yDTs is decidable, that is, we can effectively check if given two yDTs output the same string for every input. Since the existing algorithm for the equivalence problem consists of two semi-algorithms, it is impossible to estimate its computational complexity. In the case where given yDTs are linear, the equivalence can be decided in at most exponential time to the size of yDT through their ‘normal forms’ which is obtained by constructing earliest yDT and minimizing the size of it. This approach relies on properties of the longest common prefix/suffix and the periodicity of language, which has never been discussed for general yDTs. In this presentation, we study earliest yDTs as the first step of another algorithm of which computational complexity can be determined. We introduce regular-lookahead to yDTs for generalizing the construction of earliest linear yDT. It makes it possible that the rule of yDT yields string as possible as earlier.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"13","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicPageStart":"13","bibliographicIssueDates":{"bibliographicIssueDate":"2019-05-21","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicVolumeNumber":"12"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":195823,"updated":"2025-01-19T22:55:02.106244+00:00","links":{},"created":"2025-01-19T01:00:42.630541+00:00"}