{"updated":"2025-01-19T22:55:13.257961+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00195817","sets":["934:935:9619:9764"]},"path":["9764"],"owner":"44499","recid":"195817","title":["Using Algebraic Properties and Function Fusion to Evaluate Tree Accumulations in Parallel"],"pubdate":{"attribute_name":"公開日","attribute_value":"2019-05-21"},"_buckets":{"deposit":"3ed724cb-60d5-44e5-ac8c-d21c80fa81f0"},"_deposit":{"id":"195817","pid":{"type":"depid","value":"195817","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Using Algebraic Properties and Function Fusion to Evaluate Tree Accumulations in Parallel","author_link":["467653","467652"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Using Algebraic Properties and Function Fusion to Evaluate Tree Accumulations in Parallel"},{"subitem_title":"Using Algebraic Properties and Function Fusion to Evaluate Tree Accumulations in Parallel","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] parallel evaluation, accumulation parameters, macro tree transducers, function fusion, semiring, attribute evaluation","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":"The University of Tokyo"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"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/195817/files/IPSJ-TPRO1202003.pdf","label":"IPSJ-TPRO1202003.pdf"},"date":[{"dateType":"Available","dateValue":"2021-05-21"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1202003.pdf","filesize":[{"value":"403.4 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":"76edeae3-45be-4921-aaf4-db0485ac6717","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":"Akimasa, Morihata"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Akimasa, Morihata","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":"Parallel evaluation of tree processing using accumulation parameters tends to be difficult because the accumulation parameters may introduce data dependencies between computations for subtrees. Some proposals have broken these data dependencies by using algebraic properties such as associativity and commutativity, but, none has achieved both the capability of complex tree traversals like attribute grammars and a theoretical guarantee of parallel speedup. This paper proposes a tree processing language based on macro tree transducers and provides a parallel evaluation algorithm for programs written in the language. The language can express complex accumulations like attribute grammars, and moreover, the number of parallel computational steps for evaluation is proportional to the height of the input tree. This paper also shows that combining the proposed approach with function fusion for macro tree transducers leads to improvement in the parallel computational complexity. Although comparable complexity improvement can be obtained from known parallel algorithms, the proof and parallel evaluation algorithm here are remarkably simpler.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Parallel evaluation of tree processing using accumulation parameters tends to be difficult because the accumulation parameters may introduce data dependencies between computations for subtrees. Some proposals have broken these data dependencies by using algebraic properties such as associativity and commutativity, but, none has achieved both the capability of complex tree traversals like attribute grammars and a theoretical guarantee of parallel speedup. This paper proposes a tree processing language based on macro tree transducers and provides a parallel evaluation algorithm for programs written in the language. The language can express complex accumulations like attribute grammars, and moreover, the number of parallel computational steps for evaluation is proportional to the height of the input tree. This paper also shows that combining the proposed approach with function fusion for macro tree transducers leads to improvement in the parallel computational complexity. Although comparable complexity improvement can be obtained from known parallel algorithms, the proof and parallel evaluation algorithm here are remarkably simpler.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2019-05-21","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicVolumeNumber":"12"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:00:42.296663+00:00","id":195817,"links":{}}