Invention Grant
US08275730B2 Information processing apparatus, information processing method, and computer program product for reducing states in a deterministic finite state automaton
有权
信息处理装置，信息处理方法以及用于在确定性有限状态自动机中减少状态的计算机程序产品
- Patent Title: Information processing apparatus, information processing method, and computer program product for reducing states in a deterministic finite state automaton
- Patent Title (中): 信息处理装置，信息处理方法以及用于在确定性有限状态自动机中减少状态的计算机程序产品
-
Application No.: US12558761Application Date: 2009-09-14
-
Publication No.: US08275730B2Publication Date: 2012-09-25
- Inventor: Manabu Nagao
- Applicant: Manabu Nagao
- Applicant Address: JP Tokyo
- Assignee: Kabushiki Kaisha Toshiba
- Current Assignee: Kabushiki Kaisha Toshiba
- Current Assignee Address: JP Tokyo
- Agency: Oblon, Spivak, McClelland, Maier & Neustadt, L.L.P.
- Priority: JP2008-249029 20080926
- Main IPC: G06F17/00
- IPC: G06F17/00 ; G06F7/60 ; G06F7/38
Abstract:
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.
Public/Granted literature
- US20100082522A1 INFORMATION PROCESSING APPARATUS, INFORMATION PROCESSING METHOD, AND COMPUTER PROGRAM PRODUCT Public/Granted day:2010-04-01
Information query
