Given two terms and their rewriting rules, an unreachability problem proves the non-existence of a reduction sequence from one term to another. This paper formalizes a method for solving unreachability problems by abstraction; i. e. , reducing an original concrete unreachability problem to a simpler abstract unreachability problem to prove the unreachability of the original concrete problem if the abstract unreachability is proved. The class of rewriting systems discussed in this paper is called β rewriting systems. The class of β rewriting systems includes very important systems such as semi-Thue systems and Petri Nets. Abstract rewriting systems are also a subclass of β rewriting systems. A β rewriting system is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement," which are common to many rewritten objects. Each domain underlying semi-Thue systems, Petri Nets, and other rewriting systems are formalized by a β structure. A concept of homomorphisms from a β structure (a concrete domain) to a β structure (an abstract domain) is introduced. A homomorphism theorem (Theorem1)is established for β rewriting systems, which states that concrete reachability implies abstract reachability. An unreachability theorem (Corollary1) is also proved for β rewriting systems. It is the contraposition of the homomorphism theorem, i. e. , it says that abstract unreachability implies concrete unreachability. The unreachability theorem is used to solve two unreachability problems: a coffee bean puzzle and a checker board puzzle.

In order to improve microprocessor performance, we propose to utilize histories of dynamic instruction sequences. A lot of special purpose memories integrated in a processor chip hold the histories. In this paper, we describe the usefulness of using two special purpose memories: Non-Consecutive basic block Buffer (NCB) and Reference Prediction Table (RPT). The NCB improves instruction fetching efficiency in order to relieve control dependences. The RPT predicts data addresses in order to speculate data dependences. From the simulation study, it has been found that the proposed mechanisms improve processor performance by up to 49. 2%.

The Asynchronous Transfer Mode (ATM) technique has been accepted as a basis for the future B-ISDN networks. In ATM networks, all information is packetized and transferred in small packets of fixed length, called cells. The packetized information transfer, without flow control between the user and the network and the use of statistical multiplexing, results in a need of a policing mechanism to control the traffic parameters of each virtual connection in order to guarantee the required quality of service (QoS). Policing of the peak cell rate is generally not complex and can be achieved by using a cell spacer or other policing mechanisms (PMs). Monitoring of the mean cell rate is more difficult, but is intended to improve the link utilization when it has to handle bursty traffic sources. Conventional PMs, such as the Leaky Bucket Mechanism (LBM) and Window Mechanisms (WMs), are not well suited to the bursty nature of the sources supported by ATM networks, therefore intelligent PMs are needed. In this paper, we propose a Fuzzy Policing Mechanism (FPM) for multimedia applications over ATM networks. We consider the case of still picture source control. The performance evaluation via simulation shows that the FPM efficiently controls the mean cell rate of the still picture source. The proposed FPM shows a good response behavior against parameter variations and the selectivity characteristics approach very close to the ideal characteristic required for a PM. The FPM has a better characteristic compared with the LBM.

In this paper some new results for analog hardware realization of secure communication system using chaos synchronization have been presented. In particular the effect of the use of transmission line as channel has been considered assuming practical implementation. The influence of the loss of transmission line and mismatching on synchronization has been investigated in chaotic systems based on the Pecora-Carroll concept. It has been shown that desynchronization due to loss can be checked by using an amplifier with appropriate gain. Moreover the bit error rate (BER) has been evaluated in a digital communication system based on the principle of chaotic masking.

Machine learning in real-world situations sometimes starts from an initial collection of training instances; learning then proceeds off and on as new training instances come intermittently. The idea of two-phase learning has then been proposed here for effectively solving the learning problems in which training instances come in this two-stage way. Four two-phase learning algorithms based on the learning method PRISM have also been proposed for inducing rules from training instances. These alternatives form a spectrum, showing achievement of the requirement of PRISM (keeping down the number of irrelevant attributes) heavily dependent on the spent computational cost. The suitable alternative, as a trade-off between computational costs and achievement to the requirements, can then be chosen according to the request of the application domains.

We present a mechanism, named the law of the jungle (LOJ), to improve the Kohonen learning. The LOJ is used to be an adaptive vector quantizer for approximating nonstationary probability distribution functions. In the LOJ mechanism, the probability that each node wins in a competition is dynamically estimated during the learning. By using the estimated win probability, "strong" nodes are increased through creating new nodes near the nodes, and "weak" nodes are decreased through deleting themselves. A pair of creation and deletion is treated as an atomic operation. Therefore, the nodes which cannot win the competition are transferred directly from the region where inputs almost never occur to the region where inputs often occur. This direct "jump" of weak nodes provides rapid convergence. Moreover, the LOJ requires neither time-decaying parameters nor a special periodic adaptation. From the above reasons, the LOJ is suitable for quick approximation of nonstationary probability distribution functions. In comparison with some other Kohonen learning networks through experiments, only the LOJ can follow nonstationary probability distributions except for under high-noise environments.

This paper proposes a new design method of a nonlinear filtering algorithm in continuous-time stochastic systems. The observed value consists of nonlinearly modulated signal and additive white Gaussian observation noise. The filtering algorithm is designed based on the same idea as the extended Kalman filter is obtained from the recursive least-squares Kalman filter in linear continuous-time stochastic systems. The proposed filter necessitates the information of the autocovariance function of the signal, the variance of the observation noise, the nonlinear observation function and its differentiated one with respect to the signal. The proposed filter is compared in estimation accuracy with the MAP filter both theoretically and numerically.

A wireless communications system with a transmission rate of 10 Mbit/s using Japanese ISM band (2471-2497 MHz) is presented. This system employs a novel spread spectrum multiple access method named "CFO-SS (Carrier Frequency Offset-Spread Spectrum)" method. In the CFO-SS system, a single PN code is commonly assigned to all the multiple carriers, and the frequency offset between the carriers is determined by the information symbol rate, which is small as compared with the spread bandwidth of the signal. Bit error rate performance of the proposed CFO-SS system under multipath environments is investigated by computer simulation, and the performance of the CFO-SS method is confirmed for wireless LAN systems using the 2.4 GHz ISM band.

This paper proposes the reserved idle signal multiple access with collision resolution (R-ISMA/CR) protocol, which can maintain stability without being influenced by the retransmission probability. The R-ISMA/CR makes use of the multi-idle signals at the base station and the manipulating counter at the terminals. The performance of this protocol is evaluated by using the maximum throughput analysis and simulations.

This paper proposes the use, in integrated wireless systems, of the Reserved Idle Signal Multiple Access with Collision Resolution (R-ISMA/CR) protocol for applications in future multimedia mobile communications. It is applied to the integrated voice and data wireless system. Moreover, the consideration is made of the integrated voice and the low-bit video wireless system in R-ISMA/CR. To integrate video we employed not only a packed discard for video packets when the video packet delay is more than a threshold value, but also the connection packet (CP) technique for improving the channel utilization. Finally the integration of voice, data, and low-bit-video wireless system in R-ISMA/CR is considered. The performance are evaluated mainly by simulations.

In this paper, we propose a method to construct structure models of articulated objects from multiple local observations of their motion using state transition analysis of local geometric constraints. The object model is constructed by a bottom-up approach with three levels. Each level groups sensor data with a constraint among local features observed by the sensor, and constructs the local model. If the sensor data in current model conflict, the model is reconstructed. In each level, the first level estimates a local geometric feature from the local sensor data (eg. edge, feature point) The second level estimates a rigid body from the local geometric feature. The third level estimates an object from the rigid bodies. In the third level, the constraint between rigid bodies is estimated by transition states, which are motions between rigid bodies. This approach is implemented on a blackboard system.

ATM networks are proposed by CCITT as the solution for the future B-ISDN. In ATM networks, the cells are transmitted between user and network without flow control, therefore, a policing mechanism (PM) is needed to check that the source traffic doesn't exceed the negotiated parameters. The sources supported by ATM networks have a bursty nature. The control of the mean cell rate of the bursty sources is intended to increase the network utilization. The conventional PMs can't efficiently monitor the mean cell rate of bursty sources, therefore new PMs are needed. In this letter, we propose a fuzzy policing mechanism (FPM). The performance evaluation via simulations shows that the FPM efficiently controls the mean cell rate of the packet voice source. The selectivity characteristics of the FPM approach the ideal characteristic required for a PM.

This paper describes the use of direct wafer bonding technique to implement the novel concept of "free-material and free-orientation integration" which we propose. The technique is applied for various wafer combinations of an In-Ga-As-P material system with lattice- and orientation-mismatches. The properties of the bonded structures are studied in terms of the crystalline and electrical characterization. The high crystalline quality of the bonded structures with those mismatches is proved by transmission electron microscopy, and good electrical conduction was attained in some bonded structures of InP and GaAs. (001) InP-based 1.55-µm wavelength lasers are fabricated on (110) GaAs substrate by direct wafer bonding. The light-current characteristics of the lasers are almost identical to those of lasers fabricated on (001) InP and (001) GaAs substrates, while the turn-on voltage is a little bit higher due to the higher barrier height at the bonded interface. The practicability in those lasers are also examined. Furthermore, we show direct wafer bonding of a (001) InP-based structure and a (110) Si substrate with a GaAs buffer layer, aligning the cleavage planes of the InP and the Si. The results demonstrate the remarkable feasibility of using the direct wafer bonding technique to obtain integrated structures of material- and orientation-mismatched wafers with satisfactory quality.

A highly reliable network which can restore itself from network failures is one important concept for the future high capacity broadband network. In such self-healing network, flooding based failure-restoration algorithm is used to locate new routes and then to reroute failure traffic to that routes automatically when network failures such as link or node failures occur. Since the speed of this algorithm is degraded by the large amount of restoration messages produced by the process, such large volume messages should be reduced. In this paper, the scheme will be proposed, which reduces the large volume messages and efficiently selects alternative routes. In this scheme, the Message Wall will be used to filter useless restoration messages at the tandem nodes and Multi-Message Selecting method will be used to rapidly select a group of link-disjointed alternative routes from the feasible ones in each Flooding Wave sequence. The simulation results show that restoration messages are dramatically reduced and adequate alternative routes can be quickly found out.

In this paper we propose a new method for parallel execution of Prolog programs and present its implementation on a distributed memory parallel computer, Fujitsu AP1000. In our method a number of processes (named Prolog engines) explore different branches of a search tree (named tasks) in parallel, which is the same as OR-parallelism. Unlike OR-parallelism, the mapping between Prolog engines and tasks is statically determined like data parallelism. Each Prolog engine can decide which task is executed by the engine without communicating with the other engines. In many search problems, however, such static task mapping may cause imbalance on the processing time of each engine since the computational costs to explore branches may vary substantially. To cope with this issue, we devise a method to adjust the task imbalance by periodical exchanging how many tasks were processed for each engine. Also for reducing communication overhead in load balancing, we limit the scope of engines that exchange the load information each other. The effectiveness of our method is evaluated by measuring execution times for N Queens and the Traveling Salesman Problem on the AP1000. Using 512 processors, we obtained 355-fold speedup for N Queens and 343-fold speedup on the Traveling Salesman Problem.

A new magnetostrictive thin-film cantilever actuator and a new thin-film walking mechanism were developed. The actuators were made of magnetostrictive amorphous Tb-Fe and Sm-Fe thin films, deposited on the opposite sides of a polyimide film substrate. These actuators need not power supply cables because they were remotely driven by external magnetic fields. The static deflection of a 3-mm-long cantilever actuator was as large as 100 µm at 300 Oe field. Moreover the application of ac resonant frequency field of the same intensity yielded deflection of above 500 µm. The walking mechanism ran as fast as in the order of cm/s. The forward and backward running were possible depending on the frequency of applied magnetic field. Such unique characteristics suggest that magnetostrictive thin-film actuators are useful in MEMS applications.

This paper describes GaAs MMICs used in wireless LANs for spread spectrum communications on the ISM band. Both the transmitter and the receiver are incorporated inside the MMIC. In our experiment using prototypes at a center frequency of 2.45 GHz, the transmitter has a saturation output power of 21.4 dBm and the total current consumption is 131.2 mA. The receiver has a noise figure of3.2 dB and a gain of 12.2 dB.

In this paper we discuss the relation between a one-way group homomorphism and a one-way ring homomorphism. Let U,V be finite abelian groups with #U=n. We show that if there exists a one-way group homomorphism f:UV, then there exists a one-way ring homomorphism F:ZnUZnImf. We also give examples of such ring homomorphisms which are one-way under a standard cryptographic assumption. This implies that there is an affirmative solution to an extended version of the open question raised by Feigenbaum and Merrit: Is there an encryption function f such that both f(x+y) and f(xy) can be efficiently computed from f(x) and f(y)? A multiple signature scheme is also given as an application of one-way ring homomorphisms.

Co-Zr and Co-Zr-Ta amorphous films were prepared by the Kr sputtering method for use as the backlayers of Co-Cr perpendicular magnetic recording tape media. The effect of the addition of Ta to Co-Zr thin films was also investigated. Lower substrate temperature was required to prepare amorphous Co-Zr films with excellent soft magnetic properties. The relationships among Ta content X, magnetostriction constant λ and magnetic characteristics such as coercivity Hc and relative permeability µr were clarified. A method of evaluating λ of soft magnetic thin films deposited on polymer sheet substrate has been presented. Films with composition of (Co95.7Zr4.3) 100-X TaX at X of 10 at.% possessed sufficiency soft magnetic properties such as low Hc below 80 A/m and high µr above 600. Addition of Ta was effective in changing change the sign of λ from positive to negative. It was found that the negative magnetoelastic energy and the smaller λ caused the soft magnetism.

In general, multimedia files are much larger than ordinary text files because they consist of multiple monomedia. In order to process large multimedia files in real time, the file system must be able to store and access files efficiently. In th UNIX s5 file system, a multimedia file may be scattered into many disk blocks over the entire disk space, and accessing a multimedia file requires a considerable amount of time for random disk head movement. This paper proposes the internal structure of a multimedia file and its inode which is modified from UNIX s5 file system's. Also, we propose a mechanism for allocating and deallocating contiguous disk blocks for large multimedia files using the bitmap tree and compares its performance with that of the UNIX s5 file system. Our results show that the proposed mechanism reduces considerably the number of disk I/Os required to allocate and deallocate contiguous disk blocks. It also reduces the total access time for large multimedia files by approximately 95% due to the contiguous allocation of disk spaces.