This paper concerns multiple-valued logical function realized by asynchronous circuit that may have feed-back loops and its completeness problems. The first aim is to give mathematical definition of an asynchronous circuit over multiple-valued logical functions and of the realization of multiple-valued logical function by means of an asynchronous circuit. For asynchronous element, the definition of circuit construction and initialization are very sensitive. A slight modification may have a considerable influence on the completeness. We consider three types of completeness (LF-, GS-, NS-completeness) for a set of multiple-valued logical functions. The LF-completeness means completeness of logical functions realized loop-free cirucit. The GS-completeness means completeness under general initialization assumption. The NS-completeness measn completeness under initialization by input assumption. The second aim is to give a completeness criterion for each type of completeness. This aim is realized for LF-completeness in general case and GS-completeness in ternary case. A completeness criteria for GS-completeness and NS-completeness are given under strong conditions.

A clique of a graph G(V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time energy-descent optimization algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that RaCLIQUE, the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.

This paper presents a parallel move generation of a Chess machine system for achieving the purpose of reducing the number of move generation cycles. The parallel system is composed of five move generation modules which share the move generating cycles to reduce the time of building a game tree. Simulation results show that the proposed parallel move generation architecture takes about half of the number of move generation cycles to build a game tree that is the same as the one built by a sequential move generation module.

We present two efficient attribute evaluator construction methods for a wide subclass of L-attributed grammars by enumeration of attributed items during one-pass bottom-up parsing. We have already proposed a construction method of a parser/evaluator for the subclass of L-attributed grammar. However the evaluator produced by our previous method uses a great number of attributed items to evaluate all attributes of a given input string. In this paper we propose two generalized methods to reduce the number of attributed itmes used in attribute evaluation. Our methods allow us to evaluate all attributes taking advantage of the use of available lookahead information.

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

Surface discharge is widely used for industrial ozonizers and toxic gas treatments, and is noise source. In this paper, an experimental investigation from the point of view of electromagnetic compatibility (EMC) has been conducted to evaluate the noise characteristics of surface discharge combustion flue gas cleaning systems. Mechanisms of propagation, coupling and formation are proposed based on the experimental observations.

The base transit time of an Aluminum-graded-base PNp AlGaAs/GaAs heterojunction bipolar transistor (HBT) was studied in order to clarify the effect of aluminum grading in the base. Theoretical analysis using a classical drift diffusion model with velocity saturation at the base-collector junction and a high base quasielectric field (58 keV/cm) created by 20%-aluminum linear grading in a 400 base, leads to a base transit time (τb) of 0.9 ps. The base transit time is reduced by four times, compared to the base transit time of 3.6 ps without aluminum grading in the base. In order to demonstrate this advantage, we fabricated aluminum-graded-base PNp AlGaAs/GaAs heterojunction transistor which employs a 20%-aluminum linear graded 400 -wide base. The device with a 2 µm 10 µm emitter showed high RF performance with a cut-off frequency (ft) of 37 GHz and a maximum oscillation frequency (fmax) of 30 GHz at a collector current density of 3.4 104 A/cm2. Further analysis using direct parameter extraction of a small signal circuit model under the collector current density of 1.1-9.9104 A/cm2 indicated the intrinsic transit time, which is the sum of the base transit time and the collector depletion layer transit time (τSC), was as low as 2.3 ps under lowinjection level. Subtracting the collector depletion-layer transit time from the intrinsic time leads to a base transit time of 1.1 ps, which is close to the theoretical base transit time and is the shortest value ever reported. The structure is very attractive for pnp-type AlGaAs HBTs combined with Npn HBTs for complementary applications.

The synergistic effects obtained by adopting both space diversity reception and adaptive equalization play a very important role in circuit outage reduction. This paper quantitatively analyzes these synergistic effects when dispersive and flat fading occur simultaneously. Analytical results show that the synergistic effects are of the same magnitude as the adaptive equalizer improvement factor when only dispersive fading causes outage. The synergistic effects gradually disappear when noise is the predominant cause of outage.

Various kinds of new architectures have been proposed to enhance operating performance of the DRAM. This paper reviews these architectures including EDO, SDRAM, RDRAM, EDRAM, and CDRAM. The EDO slightly modifies the output control of the conventional DRAM architecture. Other innovative architectures try to enhance the performance by taking advantage of DRAM's internal multiple bits architecture with internal pipeline, parallel-serial conversion, or static buffers/on-chip cache. A quantitative analysis based on an assumption of wait cycles was made to compare PC system performance with some architectures. The calculation indicated the effectiveness of external or on-chip cache. Future trends cover high-speed I/O interface, unified memory architecture, and system integrated memory. The interface includes limited I/O swing such as HSTL and SSTL to realize more than 100MHz operation. Also, Ramlink and SyncLink are briefly reviewed as candidates for next generation interface. Unified memory architecture attempts to save total memory capacity by combining graphics and main memory. Advanced device technology enables system integration which combine system logic and memory. It suggests one potential direction towards system on a chip in the future.

This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.

A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ2, where P is a prime sufficiently smaller than Q. The result is of interest to cryptographers, since integers with secret factorization of this form are being used in digital signatures. The algorithm makes use of what we call Jacobi signatures. We believe these to be of independent interest.

Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great number of algorithms have been presented for this problem, some of which have only been evaluated just by comparison with human eyes. In this paper we formulate the digital halftoning problem as a combinatiorial problem which allows an exact solution with graph-theoretic tools. For this, we consider a d-dimensional grid of n := Nd pixels (d 1). For each pixel, we define a so-called k-neighborhood, k {0,...N - 1}, which is the set of at most (2k + 1)d pixels that can be reached from the current pixel in a distance of k. Now, in order to solve the digital halftoning problem, we are going to minimize the sum of distances of all k-neighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the one-dimensional case while it looks hopeless to have a polynomial-time algorithm in higher dimension including the usual two-dimensional case. We present an exact algorithm for the one-dimensional case which runs in O(n) time if k is regarded to be a constant. For two-dimensional case we present fast approximation techniques based on space filling curves. An experimental comparison of several implementations of approximate algorithms proves that our algorithms are of practical interest.

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.

It is demonstrated with the Berlekamp-Massey shift-register synthesis algorithm that the linear complexity value of binary complementary sequences is at least 3/4 of the sequence length. For some sequence pairs the linear complexity value can be even 0.98 times the sequence length. In the light of these results strongly non-linear complementary sequences are considered suitable for information security applications employing the spread-spectrum (SS) technique.

This paper discusses the problems of largest similar substructures (in short, LSS) in rooted and unordered trees (in short, R-trees) and those in unrooted and unordered trees (in short, trees). For two R-trees (or trees) Ta and Tb, LSS in Tb to Ta is defined, and two algorithms for finding one of the LSSs for R-trees and that for trees are proposed. The time and space complexities of both algorithms are OT (m3NaNb) and OS(mNaNb), respectively, where m is the largest degree of a vertex of Ta and Tb, and Na(Nb)is the number of vertices of Ta(Tb).

An s-t flow in a directed network is called uncontrollable, when the flow is representable as a positive sum of elementary s-t path flows. In this paper, we discuss the problem Is a given flow uncontrollable?. We show that the problem is NP-complete.

We define the Reallocation Problem to determine whether we can move products from their current store-houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.

A fast and stable algorithm for locating a desired eigenvalue and its corresponding eigenvector is presented. Its effectiveness is shown through a numerical simulation. The proposed algorithm is fast and numerically accurate enough to be applied to a real application.

Understanding unknown objects in images is one of the most important fields of the computer vision. We are confronted with the problem of dealing with the ambiguity of the image information about unknown objects in the scene. The purpose of this paper is to propose a new object recognition method based on the fuzzy relation system and the fuzzy integral. In order to deal with the ambiguity of the image information, we apply the fuzzy theory to object recognition subjects. Firstly, we define the degree of similarity based on the fuzzy relation system among input images and object models. In the next, to avoid the uncertainty of relations between the input image and the 2-D aspects of models, we integrate the degree of similarity obtained from several input images by the fuzzy integral. This proposing method makes it possible to recognize the unknown objects correctly under the ambiguity of the image information. And the validity of our method is confirmed by the experiments with six kinds of chairs.

This paper proposes a method for achieving low-power control-logic modules using a combination of CMOS complex gate reorganization, transistor size optimization, and transistor layout. Complex gate reorganization minimizes transistor count and net count without changing the functionality of the circuit. Transistor sizing and layout are interdependent, the optimization of one results in the optimization of the other. The authors applied the reorganization method to a 10,846-transistor circuit, and succeeded in reducing the transistor count by 10%, and the net count by 9%. Transistor sizing and layout compaction reduced the average transistor size by one tenth, while the same delay was maintained. Total circuit capacitance, which is strongly related to power dissipation, was cut to 36%, even when wiring capacitances were dominant.