发明授权
US08275730B2 Information processing apparatus, information processing method, and computer program product for reducing states in a deterministic finite state automaton
有权
信息处理装置，信息处理方法以及用于在确定性有限状态自动机中减少状态的计算机程序产品
- 专利标题： Information processing apparatus, information processing method, and computer program product for reducing states in a deterministic finite state automaton
- 专利标题（中）： 信息处理装置，信息处理方法以及用于在确定性有限状态自动机中减少状态的计算机程序产品
-
申请号： US12558761申请日： 2009-09-14
-
公开(公告)号： US08275730B2公开(公告)日： 2012-09-25
- 发明人: Manabu Nagao
- 申请人： Manabu Nagao
- 申请人地址： JP Tokyo
- 专利权人： Kabushiki Kaisha Toshiba
- 当前专利权人： Kabushiki Kaisha Toshiba
- 当前专利权人地址： JP Tokyo
- 代理机构： Oblon, Spivak, McClelland, Maier & Neustadt, L.L.P.
- 优先权： JP2008-249029 20080926
- 主分类号： G06F17/00
- IPC分类号： G06F17/00 ; G06F7/60 ; G06F7/38
摘要：
States included in a deterministic finite automaton are classified into states having the same input symbols associated with outgoing transitions and the same finality, and a calculates an intersection set between each of the state sets and a set of transition destination states which is obtained by translating each of states included in the state sets, until the number of states included in the intersection set becomes equal to one, while regarding the set of the transition destination states for each of the input symbol included in the intersection set as new state sets, and plural indistinguishable states are merged into one state by tracing a route in a reverse direction to a transition direction, when the number of states has become equal to one.
公开/授权文献
信息查询
