{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00072979","sets":["1164:2735:6337:6338"]},"path":["6338"],"owner":"10","recid":"72979","title":["Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ"],"pubdate":{"attribute_name":"公開日","attribute_value":"2011-02-28"},"_buckets":{"deposit":"81a6a62b-cea8-4cfd-a431-5c720c70bdf3"},"_deposit":{"id":"72979","pid":{"type":"depid","value":"72979","revision_id":0},"owners":[10],"status":"published","created_by":10},"item_title":"Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ"},{"subitem_title":"A Hybrid Approach for Exact Solving of Minimum Consistent-DFA Generation Problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2011-02-28","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"総合研究大学院大学，国立東京工業高等専門学校"},{"subitem_text_value":"東京大学，国立情報学研究所"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"The Graduate University for Advanced Studies, Tokyo National College of Technology","subitem_text_language":"en"},{"subitem_text_value":"Tokyo University, Natinal Institute of Informatics","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/72979/files/IPSJ-MPS11082001.pdf"},"date":[{"dateType":"Available","dateValue":"2013-02-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-MPS11082001.pdf","filesize":[{"value":"845.9 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"17"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"66936224-08e1-42d3-a8cc-6542806744eb","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2011 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"乾, 伸雄"},{"creatorName":"相澤, 彰子"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Nobuo, Inui","creatorNameLang":"en"},{"creatorName":"Akiko, Aizawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10505667","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本稿では，ラベル付き記号列集合から最小状態数の決定性有限状態オートマトン （DFA） を効率よく生成する手法について述べる．この問題は，NP 困難な問題と知られているが，近年の SAT ソルバーの効率化によって，専用のアルゴリズムに匹敵する計算速度が得られたことが報告された．本稿では，この手法をさらに発展させるため，対称性除去のための最大クリークを MILP ソルバーで発見する方法を導入する．また，ヒューリスティックに発見した DFA を上界，最大クリークを下界としたアルゴリズムを提案する．数値実験の結果，ベンチマーク問題に対して従来手法の 50％ の計算時間で結果が得られることがわかった．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"This paper proposes a new hybrid method for generating a minimum consistent-DFA (deterministic finite state automaton) of a set of labeled strings. Though this problem is well-known as an NP-hard problem, the recent paper reported that a SAT (satisfiability ) problem formulation could solve it efficiently and showed compatible with specialized algorithms. This paper introduces a mixed integer linear programming model to solve the maximum clique problem for symmetry breaking and use an upper-bound found by a heuristic method to use a window search. Numerical experiment showed that our method achieved 50% reduction in running time compared with the previous SAT-based method.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"研究報告数理モデル化と問題解決（MPS）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2011-02-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"2011-MPS-82"}]},"relation_version_is_last":true,"weko_creator_id":"10"},"id":72979,"updated":"2025-01-21T22:06:16.322100+00:00","links":{},"created":"2025-01-18T23:31:08.423922+00:00"}