In this paper, we study the following problem: given two graphs G, H and an isomorphism φ between an induced subgraph of G and an induced subgraph of H, compute the number of isomorphisms between G and H that do not contradict φ. We show that this problem can be solved in O(((k+1)(k+1)!)²n³) time when the input graphs are restricted to chordal graphs with clique number at most k+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in O(n³) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between G and H can be efficiently computed by use of the tree model.

Software with design flaws increases maintenance costs, decreases component reuse, and reduces software life. Even well-designed software tends to deteriorate with time as it undergoes maintenance. Work on restructuring object-oriented designs involves estimating the quality of the designs using metrics, and automating transformations that preserve the behavior of the designs. However, these factors have been treated almost independently of each other. A long-term goal is to define transformations preserving the behavior of object-oriented designs, and automate the transformations using metrics. In this paper, we describe a genetic algorithm based restructuring approach using metrics to automatically modify object-oriented designs. Cohesion and coupling metrics based on abstract models are defined to quantify designs and provide criteria for comparing alternative designs. The abstract models include a call-use graph and a class-association graph that represent methods, attributes, classes, and their relationships. The metrics include cohesion, inheritance coupling, and interaction coupling based on the behavioral similarity between methods extracted from the models. We define restructuring operations, and show that the operations preserve the behavior of object-oriented designs. We also devise a fitness function using cohesion and coupling metrics, and automatically restructure object-oriented designs by applying a genetic algorithm using the fitness function.

This paper proposes a multi-host RAID-5 architecture in which multiple hosts can access disk array via storage area network. In this configuration, parity inconsistency occurs when different hosts try to write to the same stripe simultaneously. Parity consistency can be ensured by the serialization of the writes to the same stripe with locking method. While conventional locking methods can be used, the performance is degraded in the case of large number of hosts. When multiple-reader single-writer file consistency semantic is used, most of the stripes are written exclusively by a single host, so parity inconsistency problem does not occur. By removing locking of those stripes which amounts to 95% in practical workloads, the performance becomes more scalable and 50% faster than using the conventional stripe locking methods.

For checkpointing to be practical, it has to introduce low overhead for the targeted application. As a means of reducing the overhead of checkpointing, this paper proposes a probabilistic checkpointing method, which uses block encoding to detect the modified memory area between two consecutive checkpoints. Since the proposed technique uses block encoding to detect the modified area, the possibility of aliasing exists in encoded words. However, this paper shows that the aliasing probability is near zero when an 8-byte encoded word is used. The performance of the proposed technique is analyzed and measured by using experiments. An analytic model which predicts the checkpointing overhead is first constructed. By using this model, the block size that produces the best performance for a given target program is estimated. In most cases, medium block sizes, i.e., 128 or 256 bytes, show the best performance. The proposed technique has also been implemented on Unix based systems, and its performance has been measured in real environments. According to the experimental results, the proposed technique reduces the overhead by 11.7% in the best case and increases the overhead by 0.5% in the worst case in comparison with page-based incremental checkpointing.

A method is described for improving cooperation in supervisory control and data acquisition (SCADA) systems that uses multi-agent (MA) intelligent field terminals (IFTs). The MA function of each IFT evaluates the control conditions of the overall system and the conditions of the other IFTs. To shorten the turn-around time for data transfer among IFTs, the conflicts that occur when the data processed by different IFTs is inconsistent or irregular are cooperatively and autonomously resolved by predictive agents incorporated into each IFT. Experimental results showed that this method not only provides adequate control but also reduces the load on the network and the turn-around time when the number of IFTs is less than 30.

Incremental evolution with learning (IEWL) is proposed for the development of autonomous robots, and the validity of the method is evaluated with a real mobile robot to acquire a complex task. Development of the control system for a complex task, i.e., approaching toward a target object by avoiding obstacles in an environment, is incrementally carried out in two-stage. In the first-stage, controllers are developed to avoid obstacles in the environment. By using acquired knowledge of the first-stage, controllers are developed in the second-stage to approach toward the target object by avoiding obstacles in the environment. It is found that the use of learning in conjunction with incremental evolution is beneficial for maintaining diversity in the evolving population. The performances of two controllers, one developed by IEWL and the other developed by incremental evolution without learning (IENL), are compared on the given task. The experimental results show that robust performance is achieved when controllers are developed by IEWL.

Experiments were conducted to examine an approach from language modeling side to improving noisy speech recognition performance. By adopting appropriate word strings as new units of processing, speech recognition performance was improved by acoustic effects as well as by test-set perplexity reduction. Three kinds of word string language models were evaluated, whose additional lexical entries were selected based on combinations of part of speech information, word length, occurrence frequency, and log likelihood ratio of the hypotheses about the bigram frequency. All of the three word string models reduced errors in broadcast news speech recognition, and also lowered test-set perplexity. The word string model based on log likelihood ratio exhibited the best improvement for noisy speech recognition, by which deletion errors were reduced by 26%, substitution errors by 9.3%, and insertion errors by 13%, in the experiments using the speaker-dependent, noise-adapted triphone. Effectiveness of word string models on error reduction was more prominent for noisy speech than for studio-clean speech.

In this paper, we propose topic extraction models based on statistical relevance scores between topic words and words in articles, and report results obtained in topic extraction experiments using continuous speech recognition for Japanese broadcast news utterances. We attempt to represent a topic of news speech using a combination of multiple topic words, which are important words in the news article or words relevant to the news. We assume a topic of news is represented by a combination of words. We statistically model mapping from words in an article to topic words. Using the mapping, the topic extraction model can extract topic words even if they do not appear in the article. We train a topic extraction model capable of computing the degree of relevance between a topic word and a word in an article by using newspaper text covering a five-year period. The degree of relevance between those words is calculated based on measures such as mutual information or the χ2-method. In experiments extracting five topic words using a χ2-based model, we achieve 72% precision and 12% recall for speech recognition results. Speech recognition results generally include a number of recognition errors, which degrades topic extraction performance. To avoid this, we employ N-best candidates and likelihood given by acoustic and language models. In experiments, we find that extracting five topic words using N-best candidate and likelihood values achieves significantly improved precision.

To elucidate the mechanism of topographic organization, we propose a simple topographic mapping formation model from generalized cell layer to generalized cell layer. Here generalized cell layer means that we consider arbitrary cell neighborhood relations. In our previous work we investigated a topographic mapping formation model between one dimensional cell layers. In this paper we extend the cell layer structure to any dimension. In our model, each cell takes a binary state value and we consider a class of learning principles which are extensions of Hebb's rule and Anti-Hebb's rule. We pay special attention to correlation type learning rules where a synaptic weight value is increased if pre and post synaptic cell states have the same value. We first show that a mapping is stable with respect to the correlational learning if and only if it is semi-embedding. Second, we introduce a special class of weight matrices called band type and show that the set of band type weight matrices is strongly closed and such a weight matrix can not yield a topographic mapping. Third, we show by computer simulations that a mapping, if it is defined by a non band type weight matrix, converges to a topographic mapping under the correlational learning rules.

This paper attempts to establish a theory for a general auto-associative memory model. We start by defining a new concept called supporting function to replace the concept of energy function. As known, the energy function relies on the assumption of symmetric interconnection weights, which is used in the conventional Hopfield auto-associative memory, but not evidenced in any biological memories. We then formulate the information retrieving process as a dynamic system by making use of the supporting function and derive the attraction or asymptotic stability condition and the condition for convergence of an arbitrary state to a desired state. The latter represents a key condition for associative memory to have a capability of learning from variant samples. Finally, we develop an algorithm to learn the asymptotic stability condition and an algorithm to train the system to recover desired states from their variant samples. The latter called sample learning algorithm is the first of its kind ever been discovered for associative memories. Both recalling and learning processes are of finite convergence, a must-have feature for associative memories by analogy to normal human memory. The effectiveness of the recalling and learning algorithms is experimentally demonstrated.

Studies on artificial neural network have been conducted for a long time, and its contribution has been shown in many fields. However, the application of neural networks in the real world domain is still a challenge, since nature does not always provide the required satisfactory conditions. One example is the class size imbalanced condition in which one class is heavily under-represented compared to another class. This condition is often found in the real world domain and presents several difficulties for algorithms that assume the balanced condition of the classes. In this paper, we propose a method for solving problems posed by imbalanced training sets by applying the modified large-scale neural network "CombNET-II. " CombNET-II consists of two types of neural networks. The first type is a one-layer vector quantization neural network to turn the problem into a more balanced condition. The second type consists of several modules of three-layered multilayer perceptron trained by backpropagation for finer classification. CombNET-II combines the two types of neural networks to solve the problem effectively within a reasonable time. The performance is then evaluated by turning the model into a practical application for a fog forecasting problem. Fog forecasting is an imbalanced training sets problem, since the probability of fog appearance in the observation location is very low. Fog events should be predicted every 30 minutes based on the observation of meteorological conditions. Our experiments showed that CombNET-II could achieve a high prediction rate compared to the k-nearest neighbor classifier and the three-layered multilayer perceptron trained with BP. Part of this research was presented in the 1999 Fog Forecasting Contest sponsored by Neurocomputing Technical Group of IEICE, Japan, and CombNET-II achieved the highest accuracy among the participants.

The purpose of this study is to show the chaotic features of rhythmic joint movement. Depending on the experimental conditions, one (or both) elbow angle(s) was (were) measured by one (or two) goniometer(s). Pacing was provided for six different frequencies presented in random order. When the frequency of the pace increased, the fractal dimension and first Lyapunov exponent tended to increase. Moreover, the first Lyapunov exponent obtained positive values for all of the observed data. These results indicate that there is chaos in rhythmic joint movement and that the larger the frequency, the more chaotic the joint movement becomes.