The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cette recherche propose des méthodes de calcul efficaces pour les matrices de transition dans les systèmes à événements discrets, où les matrices d'adjacence sont représentées par des graphes acycliques orientés. L'essentiel de la recherche se concentre sur l'obtention du Kleene Star d'une matrice de contiguïté. Des études antérieures ont proposé des méthodes de calcul des chemins les plus longs en se concentrant sur les nœuds de destination. Cependant, dans ces méthodes, l’algorithme choisi dépend du fait que la matrice d’adjacence soit clairsemée ou dense. En revanche, cette recherche calcule les chemins les plus longs en se concentrant sur les nœuds sources. Les méthodes proposées sont plus efficaces que les précédentes et intéressantes dans le sens où l'efficacité n'est pas affectée par la densité de la matrice d'adjacence.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hiroyuki GOTO, Hirotaka TAKAHASHI, "Fast Computation Methods for the Kleene Star in Max-Plus Linear Systems with a DAG Structure" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 11, pp. 2794-2799, November 2009, doi: 10.1587/transfun.E92.A.2794.
Abstract: This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2794/_p
Copier
@ARTICLE{e92-a_11_2794,
author={Hiroyuki GOTO, Hirotaka TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fast Computation Methods for the Kleene Star in Max-Plus Linear Systems with a DAG Structure},
year={2009},
volume={E92-A},
number={11},
pages={2794-2799},
abstract={This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.},
keywords={},
doi={10.1587/transfun.E92.A.2794},
ISSN={1745-1337},
month={November},}
Copier
TY - JOUR
TI - Fast Computation Methods for the Kleene Star in Max-Plus Linear Systems with a DAG Structure
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2794
EP - 2799
AU - Hiroyuki GOTO
AU - Hirotaka TAKAHASHI
PY - 2009
DO - 10.1587/transfun.E92.A.2794
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2009
AB - This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.
ER -