This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGs). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.

In this letter, an eigenspace of network topology is introduced to increase a spatial capacity. The network topology is represented as an adjacency matrix. By an eigenvector of adjacency matrix, efficient two way transmission can be realized in wireless distributed networks. It is confirmed by numerical analysis that the scheme with an eigenvector of adjacency matrix supplies higher spatial capacity and reliability than that of conventional scheme.

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.

This research considers an efficient method for calculating the transition matrix in an MPL (Max-Plus Linear) state-space representation. This matrix can be generated by applying the Kleene star operator to an adjacency matrix. The proposed method, based on the idea of a topological sort in graph theory and block splitting, is able to calculate the transition matrix efficiently.

In general, when many functions and services are added to a system, verification and validation become difficult. In design and development in telecommunication services, conflicts that arise from combined telecommunication services have been discussed from various viewpoints. However, correctly and efficiently detecting all conflicts is still not possible and the resolution of conflicts primarily depends on expert designers, who are finding that these problems are beyond their ability. Thus, the burden on the designer must also be alleviated at the design stage. Service interference, which is discussed in this paper, is a kind of conflict. A problem of service interference is that during service, other services interfere with the ongoing service behavior. That is to say, a strange state arises, or an input event doesn't work, or a strange transition occurs, etc. The detection of service interference by only comparing states among services is not enough since the state transition must be considered in the service interference. This paper proposes how to automatically detect the service interference with a rule-based system and an extended adjacency matrix. The proposed method uses and combines features of both the adjacency matrix and rule-based system. The method first generates the extended adjacency matrix by the rule application, then extracts sequences of the state, the event, and the rule applications, and then detects the service interference with the extracted sequences.

As a first step to develop a system to analyze or recognize patterns contained in mages, it is important to provide a good base representation that can facilitate efficiently the interpretation of such patterns. Since structural features of basic patterns in document images such as characters or tables are horizontal and vertical stroke components, we propose a new expression of document image based on the MCR expression that can express well such features of text and tabular components of an image.

An efficient technique for expressing document image is required as part of a unified approach to document image processing. This paper presents a new method, Minimum Covering Run (MCR), for expressing binary images. The name being adapted from horizontal or vertical run representation. The proposed technique uses some horizontal and vertical runs together to represent binary images in which the total number of representative runs is minimized. Considering the characteristic of above run types precisely, it is shown that horizontal and vertical runs of any binary image could be thought of as partite sets of a bipartite graph. Consequently, the MCR expression that corresponds to the construction of one of the most interesting problems in graphs; i.e., maximum matching, is analogously found by using an algorithm which solves this problem in a corresponding graph. The most efficient algorithm takes at most O(n5/2) computations for solving the problem where n is the sum of cardinalities of both partite sets. However, some patterns in images like tables or line drowings, generally, have a large number of runs representing them which results in a long processing time. Therefore, we provide the Rectangular Segment Analysis (RSA) as a pre-processing to define runs representing such patterns beforehand. We also show that horizontal and vertical covering parts of the proposed expression are able to represent stroke components of characters in document images. As an implementation, an efficient algorithm including arrangement for run data structure of the MCR expression is presented. The experimental results show the possibility of stroke extraction of characters in document images. As an application, some patterns such as tables can be extracted from document images.