In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's

In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n³/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.

In this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number δ > 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most δ under the condition that any translation and rotation can be applied to P. Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(n⁸), O((n⁷/k³) polylog(n)) and O(n⁴) respectively, where n denotes the size of larger input structure and k denotes the minimum size of the alignment to be obtained. All of these have the following common framework: a series of initial superpositions are computed; for each of such superpositions, a rough alignment is first computed using a dynamic programming technique, and then it is refined through an iterative improvement procedure which also uses dynamic programming; the best alignment among them is selected as an output. The difference among three algorithms lies in the methods of finding initial superpositions. BASICALIGN, RANDALIGN and FRAGALIGN use exhaustive search, random sampling technique and fragment-based search, respectively. We prove guaranteed approximation ratios (in the sense of distances between point pairs) for theoretical versions of BASICALIGN and RANDALIGN. Practical versions of RANDALIGN and FRAGALIGN were implemented and compared with a previous algorithm using real protein structure data. The experimental results show that FRAGALIGN is best among them and it outputs good alignments quickly.

A direct-mapped cache takes less time for accessing data than a set-associative cache because the time needed for selecting a cache line among the set is not necessary. The hit ratio of a direct-mapped cache, however, is lower due to the conflict misses caused by mapping multiple addresses to the same cache line. Addressing cache memory by virtual addresses reduces the cache access time by eliminating the time needed for address translation. The synonym problem in virtual cache necessitates an additional field in the cache tag to denote the process to which cache line belongs. In this paper, we propose a new virtual cache architecture whose average access time is almost the same as the direct-mapped caches while the hit ratio is the same as the set-associative cashes. A victim for cache replacement is selected from those that belong to a process which is most remote from being scheduled. The entire cache memory is divided into n banks, and each process is assigned to a bank. Then, each process runs on the assigned bank, and the cache behaves like a direct-mapped cache. Trace-driven simulations confirm that the new scheme removes almost as many conflict misses as does the set-associative cache, while cache access time is similar to a direct-mapped cache.

In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.

The quality of a modular software system depends on the reliabilities of the software modules and the software operational profile. When the software is designed for multiple customers having different operational profiles, different customers may experience different software quality. It is important to ensure that no customer will suffer from a poor software quality. In this paper, we formulate and solve three reliability allocation problems for modular software system designed for multiple customers. In these reliability allocation problems, we consider the software operational profile of every customer while fulfilling such practical constraints as cost budget and software quality requirement. The numerical results show that when the operational profiles of the customers are more skewed, it is more beneficial to take their operational profiles into account.

This paper provides a queueing model analysis of virtual route networks for which a pacing window flow control mechanism is employed with an input queue included. The input queue is introduced into the model to describe the waiting system where messages prevented from entering the network are stored in first-come first-serve manner. Both cases of finite and infinite capacity are considered. The model leads to a Markovian queueing system, which is fully solved through appropriate use of matrix-geometric methods. The empirical rule is that the optimum window size which maximizes the power criterion including the admission delay is nearly twice the number of hops (nodes of the network). Simulations are presented to verify the analytical results. Finally, performance comparisons with the sliding window protocol are made. Our results show that although the average number of messages in the network is higher for the pacing window case, when the input queue delay is taken into consideration the overall performance of the pacing window protocol is better than that of the sliding window.

A systematic procedure to configure faulttolerant systolic arrays based on Triplicated Triple Modular Redundancy is proposed. The design procedure consists of the triplication of the dependence graph which is formed from a target regular algorithm and the transformation onto physical time-processor domain. The resultant systolic arrays tolerate failures not only on processing elements but also on communication links. While it needs sophisticated connection scheme between processing elements to guarantee the fault-tolerance on communication links, the link complexity is possibly reduced by optimizing redundant operation scheme. Unconstrained and constrained link minimization problems are introduced, and the possibility and the constraints required for link complexity reduction are investigated.

The Time-Slicing paradigm is a newly developed method for the training of neural networks for speech recognition. The neural net is trained to spot the syllables in a continuous stream of speech. It generates a transcription of the utterance, be it a word, a phrase, etc. Combined with a simple error recovery method the desired units (words or phrases) can be retrieved. This paradigm uses a recurrent neural network trained in a modular fashion with natural connectionist glue. It processes the input signal sequentially regardless of the input's length and immediately extracts the syllables spotted in the speech stream. As an example, this character string is then compared to a set of possible words, picking out the five closest candidates. In this paper we describe the time-slicing paradigm and the training of the recurrent neural network together with details about the training samples. It also introduces the concept of natural connectionist glue and the recurrent neural network's architecture used for this purpose. Additionally we explain the errors found in the output and the process to reduce them and recover the correct words. The recognition rates of the network and the recovery rates for the words are also shown. The presented examples and recognition rates demonstrate the potential of the time-slicing method for continuous speech recognition.

This paper describes how to effectively use discriminative training based on Minimum Classification Error (MCE) criterion for a small amount of data in order to attain the highest level of recognition performance. This method is a combination of MCE training and Vector-Field-Smoothed Bayesian learning called MAP/VFS, which combines maximum a posteriori (MAP) estimation with Vector Field Smoothing (VFS). In the proposed method, MAP/VFS can significantly enhance MCE training in the robustness of acoustic modeling. In model training, MCE training is performed using the MAP/VFS-trained model as an initial model. The same data are used in both trainings. For speaker adaptation using several dozen training words, the proposed method has been experimentally proven to be very effective. For 50-word training data, recognition errors are drastically reduced by 47% compared with 16.5% when using only MCE. This high rate, in which 39% is due to MAP, an additional 4% is due to VFS, and a further improvement of 4% is due to MCE, can be attained by enhancing MCE training capability by MAP/VFS.

A method of motion segmentation in RGB image sequences is presented in details. The method is based on moving object modeling by a six-variate Gaussian distribution and a hidden Markov random field (MRF) framework. It is an extended and improved version of our previous work. Based on mathematical principles the energy expression of MRF is modified. Moreover, an initialization procedure for the first frame of the sequence is introduced. Both modifications result in new interesting features. The first involves a rather simple parameter estimation which has to be performed before the use of the method. Now, the values of Maximum Likelihood (ML) estimators of the parameters can be used without any user's modifications. The last allows one to avoid finding manually the localization mask of moving object in the first frame. Experimental results showing the usefulness of the method are also included.

A requirement specification acquisition method combined with hypothesis-based reasoning and model reasoning is proposed for obtaining service specifications from the ambiguous and/or incomplete requirement specifications of communications services. Errors at an early stage of software development cost more to debug than those at a later stage. Specification acquisition is the most upstream development process. Nevertheless, the system support for specification acquisition is delayed compared with other development phases.' Users do not always have precise requirements. It is therefore inevitable that user requirements contain ambiguities, insufficiencies and even contradictions. Considering this, it is indispensable to support a specification completion method that derives service specifications from such problem requirements. This paper proposes a combined method to obtain consistent and complete specifications from such problem requirements. Communications service specifications can be described by specifying terminal behaviors which can be recognized from outside the communications system(s). Such specifications are described by a rule-based language. Requirement specifications usually have components that are ambiguous, incomplete, or even contradictory. They appear as rule description and/or missing rules. From such requirements, service specifications are obtained by using hypothesis-based reasoning on input requirements and existing service specifications. When existing specifications cannot be used to obtain complementary specifications, a communications service model is used to propose new rules. The proposed methods are implemented as a part of a communications software development system. The system enables non-experts in communications systems to define their own service specifications.