2021-06-18T09:52:01Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000707292020-10-27T05:02:56Z00934:00989:06006:06192
State and Threshold Sequence Minimization Algorithm of Linear Separation AutomataState and Threshold Sequence Minimization Algorithm of Linear Separation Automataengオリジナル論文http://id.nii.ac.jp/1001/00070729/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=70729&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of JapanDepartment of Computer Science, Graduate School of Electro-Communications, University of Electro-CommunicationsNTT-IT CorporationDepartment of Computer Science, Graduate School of Electro-Communications, University of Electro-CommunicationsYuji, NumaiYoshiaki, UdagawaSatoshi, KobayashiIn this paper, we present a minimization algorithm of the number of states of a linear separation automaton (LSA). An LSA is an extended model of a finite automaton. It accepts a sequence of real vectors, and has a weight and a threshold sequence at every state, which determine the transition from the current state to the next at each step. In our previous paper, we characterized an LSA and the minimum state LSA. The minimum state version for a given LSA M is obtained by the algorithm presented in this paper. Its time complexity is O((K + k)n2), where K is the maximum number of threshold values assigned to each weight, k is the maximum number of edges going out from a state of M, and n is the number of states in M. Moreover, we discuss the minimization of a threshold sequence at each state.In this paper, we present a minimization algorithm of the number of states of a linear separation automaton (LSA). An LSA is an extended model of a finite automaton. It accepts a sequence of real vectors, and has a weight and a threshold sequence at every state, which determine the transition from the current state to the next at each step. In our previous paper, we characterized an LSA and the minimum state LSA. The minimum state version for a given LSA M is obtained by the algorithm presented in this paper. Its time complexity is O((K + k)n2), where K is the maximum number of threshold values assigned to each weight, k is the maximum number of edges going out from a state of M, and n is the number of states in M. Moreover, we discuss the minimization of a threshold sequence at each state.AA11464803情報処理学会論文誌数理モデル化と応用（TOM）3367792010-10-251882-77802010-10-21