WEKO3
-
RootNode
アイテム
Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ
https://ipsj.ixsq.nii.ac.jp/records/72979
https://ipsj.ixsq.nii.ac.jp/records/729794fa1f913-90cc-4bba-9021-559749f5ee31
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2011-02-28 | |||||||
タイトル | ||||||||
タイトル | Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A Hybrid Approach for Exact Solving of Minimum Consistent-DFA Generation Problem | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
総合研究大学院大学,国立東京工業高等専門学校 | ||||||||
著者所属 | ||||||||
東京大学,国立情報学研究所 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
The Graduate University for Advanced Studies, Tokyo National College of Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Tokyo University, Natinal Institute of Informatics | ||||||||
著者名 |
乾, 伸雄
× 乾, 伸雄
|
|||||||
著者名(英) |
Nobuo, Inui
× Nobuo, Inui
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 本稿では,ラベル付き記号列集合から最小状態数の決定性有限状態オートマトン (DFA) を効率よく生成する手法について述べる.この問題は,NP 困難な問題と知られているが,近年の SAT ソルバーの効率化によって,専用のアルゴリズムに匹敵する計算速度が得られたことが報告された.本稿では,この手法をさらに発展させるため,対称性除去のための最大クリークを MILP ソルバーで発見する方法を導入する.また,ヒューリスティックに発見した DFA を上界,最大クリークを下界としたアルゴリズムを提案する.数値実験の結果,ベンチマーク問題に対して従来手法の 50% の計算時間で結果が得られることがわかった. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 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. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN10505667 | |||||||
書誌情報 |
研究報告数理モデル化と問題解決(MPS) 巻 2011-MPS-82, 号 1, p. 1-6, 発行日 2011-02-28 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |