Fast Computation Methods for the Kleene Star in Max-Plus Linear Systems with a DAG Structure
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2794-2799
- Publication Date
- 2009/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.2794
- Type of Manuscript
- Special Section LETTER (Special Section on Theory of Concurrent Systems and its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
