@techreport{oai:ipsj.ixsq.nii.ac.jp:00072979,
 author = {乾, 伸雄 and 相澤, 彰子 and Nobuo, Inui and Akiko, Aizawa},
 issue = {1},
 month = {Feb},
 note = {本稿では，ラベル付き記号列集合から最小状態数の決定性有限状態オートマトン （DFA） を効率よく生成する手法について述べる．この問題は，NP 困難な問題と知られているが，近年の SAT ソルバーの効率化によって，専用のアルゴリズムに匹敵する計算速度が得られたことが報告された．本稿では，この手法をさらに発展させるため，対称性除去のための最大クリークを MILP ソルバーで発見する方法を導入する．また，ヒューリスティックに発見した DFA を上界，最大クリークを下界としたアルゴリズムを提案する．数値実験の結果，ベンチマーク問題に対して従来手法の 50％ の計算時間で結果が得られることがわかった．, 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.},
 title = {Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ},
 year = {2011}
}