A Fast Computation of the State Vector in a Class of DES System

摘要

We propose an efficient algorithm for computing the state vector of a state equation in Dioid algebra. When calculating the earliest event occurrence times for a system in which the precedence relationships are represented by a directed acyclic graph, the time complexity of computing the transition matrix is the bottleneck. The matrix can be calculated using the Kleene star operation, the time complexity of which, with the most efficient algorithm proposed thus far, is O(n~*(n+m)), where n and m represent the number of nodes and arcs, respectively. However, the primary focus in calculating the state equation is the multiplication of the transition matrix and state vector, rather than calculating the transition matrix itself. In view of this, this research proposes an algorithm for efficiently calculating the multiplication or left division of the Kleene star for an adjacency matrix and a vector. Once the topological relationships of the adjacency matrix have been obtained, the resulting vector can be computed with O(m) time complexity.