A subclass of context-free languages, called pure context-free languages, which is generated by context-free grammar with only one type of symbol (i.e., terminals and nonterminals are not distinguished), is introduced and the problem of identifying from positive data a restricted class of monogenic pure context-free languages (mono-PCF languages, in short) is investigated. The class of mono-PCF languages is incomparable to the class of regular languages. In this paper we show that the class of mono-PCF languages is polynomial time identifiable from positive data. That is, there is an algorithm that, given a mono-PCF language L, identifies from positive data, a grammar generating L, called a monogenic pure context-free grammar (mono-PCF grammar, in short) satisfying the property that the time for updating a conjecture is bounded by O(N3), where N is the sum of lengths of all positive data provided. This is in contrast with another result in this paper that the class of PCF languages is not identifiable in the limit from positive data.

A method is presented for detecting impulsive noises in chaotic time series, based on a new nonlinear prediction algorithm. A multi-dimensional trajectory is reconstructed from a time series using delay coordinates. The future value of a point on the trajectory is predicted using a local approximation technique revised by adding the Biweight estimation method and then the prediction error is calculated. Impulsive noises are detected by examining the prediction errors for all points on the trajectory. The proposed method is applied to the time series of the pupil area and the refractive power of the lens in the human eye. The Lyapunov exponent analysis for thses time series is conducted. As a result, it is shown that the proposed method is effective in detecting impulsive noises caused by blinking in these time series.

Entire systems on a chip (SOCs) embodying a processor, memory, and system-specific peripheral hardware are now an everyday reality. The current generation of SOC designers are driven more than ever by the need to lower chip cost, while at the same time being faced with demands to get designs to market more quickly. It was to support this new community of designers that we developed Satsuki-an integrated processor synthesis and compiler generation system. By allowing the designer to tune the processor design to the bitwidth and performance required by the application, minimum cost designs are achieved. Using synthesis to implement the processor in the same technology as the rest of the chip, allows for global chip optimization from the perspective of the system as a whole and assures design portability. The integral compiler generator, driven by the same parameters used for processor synthesis, promotes high-level expression of application algorithms while at the same time isolating the application software from the processor implementation. Synthesis experiments incorporating a 0.8 micron CMOS gate array have produced designs ranging from a 45 MHz, 1,500 gate, 8-bit processor with a 4-word register file to a 31 MHz, 9,800 gate, 32-bit processor with a 16-word register file.

3D model-based coding methods that need 3D reconstruction techniques are proposed for next-generation image coding methods. A method is presented that reconstructs 3D shapes of dynamic objects from image sequences captured using two cameras, thus avoiding the stereo correspondence problem. A coaxial camera system consisting of one moving and one static camera was developed. The optical axes of both cameras are precisely adjusted and have the same orientation using an optical system with true and half mirrors. The moving camera is moved along a straight horizontal line. This method can reconstruct 3D shapes of static objects as well as dynamic objects using motion vectors calculated from the moving camera images and revised using the static camera image. The method was tested successfully on real images by reconstructing a moving human shape.

This paper addresses the problem of estimating 3-D motion of a rigid object from a sequence of monocular 2-D images. The surface of object is assumed to be modeled with several patches, each of which is expressed by an implicit equation. The proposed method estimates the pose (i.e., the location and orientation) of object that corresponds to each image in the sequence: The sequence of the estimated poses gives the motion of the object. The estimation is done by solving a system of equations, each of which is typically an algebraic equation of low degree, that is derived from the expressions of the surface patches and image contours data: so the method does not require establishing the correspondence between successive two frames in the image sequence or computing optic flow. Allowing several-patch models for objects enables the proposed approach to deal with a great variety of objects. The paper includes a numerical example, where our aproach has been applied to a polyhedral object modeled with several patches.

A new application of the factorization method is reported for 3-D shape reconstruction from endoscope image sequences. The feasibility of the method is verified with some theoretical considerations and results of extensive experiments. This method was developed by Tomasi and Kanade, and improved by Poelman and Kanade, with the aim of achieving accurate shape reconstruction by using a large number of points and images, and robustly applying well-understood matrix computations. However, the latter stage of the method, called normalization, is not as easily understandable as the use of singular value decomposition in the first stage. In fact, as shown in this report, many choices are possible for this normalization and a variety of results have been obtained depending on the choice. This method is easy to understand, easy to implement, and provides sufficient accuracy when the approximation used for the optical system is reasonable. However, the details of the theoretical basis require further study.

A quasi-optical Superconductor-Insulator-Superconductor (SIS) mixer has been designed and tested in the 270-GHz band. The mixer used a substrate-lens-coupled log-periodic antenna and a tuning circuit for RF matching. The antenna is planar and self-complementary, and has a frequency-independent impedance of around 114 Ω over several octaves. The tuning circuit consists of two Nb/AIOx/Nb tunnel junctions separated by inductance for tuning out the junction capacitances and a λ/4 impedance transformer for matching the resistance of the two-junction circuit to the antenna impedance. The IF output from the mixer is brought out in a balanced method at each edge of the antenna, and is coupled to a low noise amplifier through a balun transformer using a 180-degree hybrid coupler for broadband IF matching. Double sideband receiver noise temperatures, determined from experimental Y-factor measurements, are about 150 K across the majority of the desired operating frequency band. The minimum receiver noise temperature of 120 K was measured at 263 GHz, which is as low as that of waveguide receivers. At this frequency, measurement of the noise contribution to the receiver results in input losses of 90 K, mixer noise of 17 K, and multiplied IF noise of 13 K. We found that the major sources of noise in our quasi-optical receiver were the optical losses.

M-ary orthogonal keying (MOK) systems under carrier frequency offset (CFO) are investigated. It is shown that spurious signals are introduced by the offset frequency components of spectrum after multiplication in correlation detection process, and some conditions on robust orthogonal signal sets are derived. Walsh function sets are found to be very weak against CFO, since they produce large spurious signals. As robust orthogonal signal sets against CFO, the rows of circulant Hadamard matrices are proposed and their error performanses are evaluated. The results show that they are good M-ary orthogonal signal sets in the presence of CFO.

For the dependent protocols to perform the server-aided RSA secret computation, the damage caused by the active attacks is greater than that by the passive attacks. Though there are two dependent proposed protocols against active attacks, the cost of the two protocols is still high. In this paper, we propose two efficient dependent protocols. Even considering the low cost of these two protocols, they can also guard against the proposed active attacks.

We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.

Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.

Many numerical simulation problems of natural phenomena are formulated by large tridiagonal and block tridiagonal linear systems. In this paper, an efficient parallel algorithm to solve a tridiagonal linear system is proposed. The algorithm named bi-recurrence algorithm has an inherent parallelism which is suitable for parallel processing. Its time complexity is 8N - 4 for a tridiagonal linear system of order N. The complexity is little more than the Gaussian elimination algorithm. For parallel implementation with two processors, the time complexity is 4N - 1. Based on the bi-recurrence algorithm, a VLSI oriented tridiagonal solver is designed, which has an architecture of 1-D linear systolic array with three processing cells. The systolic tridiagonal solver completes finding the solution of a tridiagonal linear system in 3N + 6 units of time. A highly parallel systolic tridiagonal solver is also presented. The solver is characterized by highly parallel computability which originates in the divide-and-conquer strategy and high cost performance which originates in the systolic architecture. This solver completes finding the solution in 10(N/p) + 6p + 23 time units, where p is the number of partitions of the system.

The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.

A laser power optimizing method for multi-pulse recording is described. Multi-pulse recording uses the recording pulse formed by bias part and comb part. To obtain best readout signal characteristics and reduce the time for optimizing, new mark pattern is recorded and then two parts of the recording pulse are individually adjusted by evaluating the detected signals during pre-write testing. At the optimized laser power by this method, a good qualitative eyepattern was obtained. As a result, this new method proves to be suitable for the multi-pulse recording and adapted to various disks with different recording properties.

This paper describes a trial of evaluating the proper characteristics of multiple sound insulatain systems from their output responses contaminated by unknown background noises. The unknown parameters of sound insulation systems are first estimated on the basis of hte linear time series on an intensity scale, describing functionally the input-output relation of the systems. Then, their output probability distributions are predicted when an arbitrary input noise passes through these insulation systems.

The use of high-performance portable computers has become widespread. It is expected that many people will carry large amounts of multimedia information in these portable computers. In face-to-face communication, however, few systems are capable of exchanging multimedia information. Previously, we developed the Nomadic Collaboration Support System, which supports face-to-face communication through conversation and the distribution of documents. The system makes it possible for each participant in face-to-face communication to distribute electronic documents to other participants and edit them synchronously. However, it is often impossible for participants to obtain suitable amounts of information during face-to-face communication because of the difficulty in tailoring the documents for each participant. In this paper, we propose a technique to exchange hypertext documents on the Nomadic Collaboration Support System, which will allow each participant to obtain the most suitable amount of information possible from the distributor without his tailoring documents for each participant.

This paper discusses a massively parallel interconnection scheme for multithreaded architecture and introduces a new class of direct interconnection networks called the hierarchical Multidimensional Directed Cycles Ensemble (hMDCE). Its suitability for massively parallel systems is discussed. The network is evolved from the Multidimensional Directed Cycles Ensemble (MDCE) network, where each node is substituted by lower-level sub-networks. The new network addresses some serious problems caused by the increasing scale of parallel systems, such as longer latency, limited throughput and high implementation cost. This paper first introduces the MDCE network and then presents and examines in detail the hierarchical MDCE network. Bisection bandwidth of hMDCE is considerably reduced from its ancestor MDCE and the network performs significantly higher throughput and lower latency under some practical implementation constraints. The gate count and delay time of the compiled circuit for the routing function are insignificant. These results reveal that the hMDCE network is an important candidate for massively parallel systems interconnection.

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.

An attenuation correction method was proposed for laser-produced plasma emission computed tomography (ECT), which is based on a relation of the attenuation coefficient and the emission coefficient in plasma. Simulation results show that the reconstructed images are dramatically improved in comparison to the reconstructions without attenuation correction.

In this paper, we analyze the throughput and delay performances of the CDMA unslotted ALOHA system considering packet retransmisson. We also clarify the stability of the system. Based on these results, we propose the optimal retransmission control (ORC) to improve the performances. The ORC is the scheme to prevent the system from drifting to an undesirable operating point by controlling the birth rate of retransmitted packets. As a result, it is shown that the throughput and delay performances of the system with the ORC are better than without the ORC and the system does not drift to an undesirable operating point.