For reversal complexity on an off-line Turing machine, which is a Turing machine with a read-only two-way input tape except work-tapes, we can consider two kinds of definition; the first one is a definition in which the number of reversals over the input tape is not counted, and the second one is a definition in which it is counted. Unlike time and space complexities, whether or not there is any difference between these two definitions does not seem to be trivial. In this paper, we will show the following results: (1) let S(n) be any function, and R(n) be an (R(n), S(n)) reversal-space constructible function. Then, DRESPk(R(n), S(n)) IDRESPk+2(R(n) + log(nS(n)), n2R(n)S(n)), (2) let R(n) and S(n) be any functions. Then, NRESPk(R(n), S(n)) INRESPk+1(R(n), n2S(n)), and ARESPk(R(n), S(n)) = IARESPk(R(n), S(n)), where DRESP denotes a deterministic reversal- and space-bounded class under the definition disregarding reversals over the input tape, and IDRESP denotes a deterministic reversal- and space-bounded class under the definition counting it. The suffix k denotes the number of work-tapes. The classes NRESP, INRESP, ARESP and IARESP are also defined similarly for NTMs and ATMs.

Petri nets are widely recognized as a powerful model for discrete event systems. Petri nets have both graphical and mathematical features. Graphical feature provides an environment to design and to comprehend discrete event systems. Mathematical feature provides an analysis power for verifying several properties of such systems. Several analysis techniques have been proposed so far, such as a reachability (coverability) graph method, a matrix equation approach, reduction or decomposition techniques, a symbolic model method and an unfolding method. The unfolding method was introduced to avoid generating the reachability graph. Unfoldings are often used in the verification of asynchronous circuits. This paper focuses on an analysis of finite state systems, i.e., bounded nets, and discuss a reachability problem and a upper bound problem. Relations between these problems and an unfolding have been clarified to provide a novel method to resolve these problems.

Synthesis tools are now extensively used in the VLSI circuit design process. They allow a much higher design productivity, but the designer often does not directly control the circuit structure. Thus, when circuits are dedicated to dependable applications, designers have difficulties in implementing manually the devices needed to obtain fault detection or tolerance capabilities. The ASYL-SdF System has been developed over the last few years in order to avoid this break in the design flow, and to facilitate the designer's work when dependability is targeted. This paper gives an overview of the resulting tool, its synthesis flow for fault detection and fault tolerance in Finite State Machines, its limitations and the current developments. Actual circuit implementation results are given in terms of area overheads, expected reliability and experimental fault detection coverage.

Because the match phase in OPS5-type production systems requires most of the system's execution time and memory accesses, we proposed hash-based parallel production systems, CPPS (Clustered Parallel Production Systems), based on the RETE algorithm for distributed memory parallel computers, or multicomputers to reduce such a bottleneck. CPPS was effective in speeding up the match phase, but still left room for optimizations. In this paper, we introduce software cache techniques to memory nodes in the CPPS as one of the optimizations, and implement it on a multicomputer, nCUBE2. The benchmark results show that the CPPS with the software cache is about 2-fold faster than the original, and more than 7-fold faster than the simple hash method proposed by Acharya et al. for a large scale problem. The speed-up can be attributed to decreased communication costs.

This paper proposes a hierarchical parallel processing system for the multipass rendering method. The multipass rendering method based on the integration of radiosity and ray-tracing can synthesize photo-realistic images. However, the method is also computationally expensive. To accelerate the multipass rendering method, the system, called (Mπ)2, employs two kinds of parallel processing schemes. As a coarse-grain parallel processing, object-space parallel processing with multiple processing elements based on the object-space subdivision is adapted, and each processing element (PE) is equipped with multiple pipelined units for a fine-grain parallel processing. To balance load among the system, static load balancing at the PE level and dynamic load balancing at the pipelined unit level within the PE are introduced. Especially, we propose a novel static load allocation scheme, skewed-distributed allocation, which can effectively distribute a three-dimensional object space to one- or two-dimensional processor configuration of the (Mπ)2 system. Simulation experiments show that the two-dimensional (Mπ)2 systems with the skewed-distributed allocation outperform the three-dimensional systems with the non-skewed distributed allocation. Since lower dimensional systems can be built at a lower cost than higher dimensional systems, the skewed-distributed allocation will be meritorious. Besides, by the combination of static load balancing by the skewed-distributed allocation and the dynamic load balancing by dynamic ray allocation within each PE, the system performance can be further boosted. We also propose a cached frame buffer system to relieve access collision on a frame buffer.

In this paper, we propose an analytic model using a semi-markov process for parallel computers which provides hardware support for a cache coherence mechanism. The model proposed here, the Semi-markov Memory and Cache coherence Interference model, can be used for the performance prediction of cache coherence based parallel computers since it can be easily applied to descriptions of the waiting states due to network contention or memory interference of both normal data accesses and cache coherence requests. Conventional analytic models using stochastic processes to describe parallel computers have the problem of numerical explosion in the number of states necessary as the system size increases even for simple parallel computers without cache coherence mechanisms. The number of states required by constructing our proposing analytic model, however, does not depend on the system size but only on the kind of cache coherence protocol. For example, the number of states for the Synapse cache coherence protocol is only 20, as is described in this paper. Using the proposed analytic model, we investigate several comparative experiments with widely known simulation results. We found that there is only a 7.08% difference between the simulation and our analytic model, while our analytic model can predict the performance of a 1,024 processor system in the order of microseconds.

This paper discusses how to derive message sequence charts (MSCs) from a set of state transition descriptions. Recently, MSC notation has received much attention in the communications software field because it graphically shows system global behavior, So MSC handling techniques are being widely studied. These studies have recommended the design a system by a set of formal MSCs in the early stages of development and then to convert them into state transition descriptions. However, it is difficult to apply those results to existing communications software products. This is because these systems are designed based on state transition descriptions and there are no formal MSCs for them. In this paper, we propose a method of deriving MSCs based on optimized reachability analysis. This method generates MCSs that avoid state explosion. A case study using Q.931 protocol shows the feasibility of this method.

This parer describes high-speed CMOS SRAM circuit technologies used in cache memories. In recent years, high-speed SRAM technology has led to higher cycle frequencies, but the rate of increase in the SRAM density has slowed. Operating modes of high-speed SRAMs are compared and the advantage of wave-pipelined SRAMs in terms of cycle frequency is shown. Three types of sense amplifiers used in SRAMs are also compared from the viewpoint of speed and power dissipation. Current sense amplifiers provide high-speed operation with low power dissipation, while latch-type sense amplifiers appear most suitable for ultra-low-power SRAMs. Low voltage operation and size reduction of full CMOS cells are now the most pressing issues in the development of SRAMs for cache memories.

Handwritten character recognition has been increasing its importance and has been expanding its application areas such as office automation, postal service automation, automatic data entry to computers, etc. It is challenging to develop a handwritten character recognition system with high processing speed, high performance, and high portability, because there is a trade-off among them. In current technology, it is difficult to attain high performance and high processing speed at the same time with single algorithms, and therefore, we need to find an efficient way of combination of multiple algorithms. We present an engineering solution to this problem. The system is based on multi-stage strategy as a whole: The first stage is a simple, fast, and reliable recognition algorithm with low substitution-error rate, and data of high quality are recognized in this stage, whereas sloppily written or degraded data are rejected and sent out to the second stage. The second stage is composed of a sophisticated structural pattern classifier and a pattern matching classifier, and these two complementary algorithms run in parallel (multiple expert approach). We demonstrate the performance of the completed system by experiments using real data.

There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.

Among three factors mainly affecting the cache access time, i. e., hit access time, miss rate and miss penalty, previous approaches were focused on reducing the hit access time and miss rate. In this paper, we propose a scheme called MPC (Miss-Predicting Cache) which achives additional reduction of the average instruction cache access time through reducing the miss penalty. The MPC scheme which predicts cache miss and starts cache miss operations in advance, therefore, is supplementary to previous cache schemes targeted for reducing the miss rate and/or hit access time. Performance of the MPC scheme was evaluated using dinero, a trace-driven cache simulator, with the estimation of silicon area using 0.8 µm CMOS standard cell library.

A novel method of multichannel surface EMG processing has been developed to compensate for the distortion in bipolar surface EMG signals due to the movement of innervation zones. The distortion of bipolar surface EMG signals was mathematically described as a filtering function. A compensating technique for such distorted bipolar surface EMG signals was developed for the brachial biceps during dynamic contractions in which the muscle length and tension change. The technique is based on multichannel surface EMG measurement, a method for estimating the movement of an innervation zone, and the inverse filtering technique. As a result, the distorted EMG signals were compensated and transformed into nearly identical waveforms, independent of the movement of the innervation zone.

In order to solve problems efficiently on a a quantum Turing machine, measurements (i. e., observations of physical systems) have been effectively used. In this paper, however, we show that the measurements executed during computation on the quantum Turing machine are not effective.

In ATM networks Connection Admission Control (CAC) is a key part of traffic control but several challenging problems still remain. One is how to assign sufficient bandwidth fast enough to achieve real-time CAC. Although solutions to the bandwidth assignment problem have been proposed, they require a lot of calculations depending on the number of VCs and on the number of different VC types. Therefore, it is difficult to apply these solutions to real-time CAC decisions, This paper presents a cell-loss ratio evaluation algorithm that takes the peak and the average cell rates as inputs, and providers the upper-bound of the cell-loss ratio. The most remarkable characteristic of this algorithm is that it does not require exhaustive calculation and its calculation load is independent of the number of VCs and the number of different VC types. Using this approximation, we propose a real-time CAC. The experimental results show that call processing of the proposed CAC using a processor, whose pertormance is almost the same as that of a processor in a conventional PBX, terminates within several milliseconds.

An invertible length preserving transducer is called a weakly invertible finite automaton (WIFA for short). If the first letter of any input string of length τ + 1 is uniquely determined by the corresponding output string by a WIFA and its initial state, it is called a WIFA with delay τ. The composition of two WIFAs is the natural concatenation of them. The composition is also a WIFA whose delay is less than or equal to the sum of the delays of the two WIFAs. In this paper we derive various results on a decomposition of a WIFA into WIFAs with smaller delays. The motivation of this subject is from theoretical interests as well as an application to cryptosystems. In order to capture the essence of the decomposability problem, we concentrate on WIFAs such that their input alphabets and their output alphabets are identical. A WIFA with size n of the input and output alphabet is denoted by an n-WIFA. We prove that for any n > 1, there exists an n-WIFA with delay 2 which cannot be decomposed into two n-WIFAs with delay 1. A one-element logic memory cell is a special WIFA with delay 1, and it is called a delay unit. We show that for any prime number p, every strongly connected p-WIFA with delay 1 can be decomposed into a WIFA with delay 0 and a delay unit, and that any 2-WIFA can be decomposed into a WIFA wiht delay 0 and a sequence of k delay units if and only if every state of the 2-WIFA has delay k.

This paper proposes a novel optical modulator for a millimeter wave (MMW) subcarrier optic link. The modulator enables the bi-phase modulation of MMW subcarriers. It simplifies the optic link by unifying such functions as IF modulation, up-convertion to MMW, and optical modulation, which are separately equipped in a conventional system. A simple model of a Mach-Zehnder external optical modulator (EOM) is used to illustrate how bi-phase modulation of millimeter wave (MMW) subcarriers can be accomplished by switching the EOM bias with a binary data signal. Experimental results are presented to confirm predictions. A wideband communications test system employing the EOM as a bi-phase modulator and utilizing spread spectrum modulation (1.3 µm optical wavelength, 40 GHz subcarrier, 100 MHz chip rate, 10MHz data rate) was developed. Bit error rate (BER) characteristics of an optical link that includes the proposed modulator are presented and compared with ideal performance and simulated predictions. Degradation of the BER characteristics from the simulation was less than 1 dB at a BER of 10-6. A frequency doubling subcarrier bi-phase modulator is also described.

In order to ensure the reliability and safety of equipment installed in process lines, it is important that maintenance and management should make efficient use of machine diagnosis techniques. Machine diagnosis by means of acoustic signals has hitherto been beset with difficulty, but there is now a strong demand that new acoustic type diagnosis equipment (utilizing acoustic signals) be developed. In response to this demand, the authors recently conducted research on diagnosis of machine faults by means of the processing of acoustic signals. In this research they were able to develop new acoustic type machine diagnosis techniques, and, using these techniques, to develop acoustic diagnosis equipment for practical use.

Mathematical morphology is inheriently suitable for range image processing because it can deal with the shape of a function in a natural and intuitive way. In this paper, a new approach to the extraction of the corner-edge-surface structure from 3D range images is proposed. Morphological operations are utilized for segmenting range images into smooth surface regions and high-variation surface regions, where the high-variation surface regions are further segmented into regions of edge type and regions of corner type. A new 3D feature, HV-skeleton, can be extracted for each high-variation surface region. The HV-skeletons can be thought of as the skeletons of high-variation surface regions and are useful for feature matching. The 3D features extracted by our approach are invariant to 3D translations and rotations, and can be utilized for higher-level vision tasks such as registration and recognition. Experimental results show that the new 3D feature extraction method works well for both simple geometric objects and complex shaped objects such as human faces.

The disturbance-rejection problem is to find a feedback control law for linear control systems such that the influence of disturbances is completely rejected from the output. In 1970 Wonham and Morse first studied this problem in the framework of the so-called geometric approach. On the other hand, in 1985 Ghosh studied parameter insensitive disturbance-rejection problems with state feedback and with dynamic compensator. In this paper we study the parameter insensitive disturbance-rejection problem with static incomplete-state feedback for linear multivariable systems in the framework of the geometric approach from the mathematical point of view. Necessary conditions and/or sufficient conditions for this problem to be solvable are presented. Finally an illustrative example is presented.

In this paper, a new optimum input encoding algorithm with m-out-of-2m code which is called Half-Hot Code is presented. By applying Half-Hot Code to the input encoding in PLA-based digital system, the logic functions of the system turn out to be unate functions, thus, the number of bit-lines of PLA may be reduced. The proposed method further reduces the number of product-lines of PLA optimally. In this code assignment procedure, computed Boolean subspaces satisfying suggeset two conditions are assigned to each partitioned subset of digital input variables which are obtained by disjoint minimization or other techniques. As an experiment to evaluate the method, the state assignment for finite state machines of two-lavel implementation is considered. Specifically, the proposed Half-Hot Code assignment is compared with arbitrary Half-Hot Code assignment. The results show that the optimum encoding is superior to an arbitrary assignment up to about 24% in the number of product-lines of PLA.