Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ*Σ* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L1 in L' over Γ such that L=h(DL1). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L2 in L' over ΣXk such that L=Red(L2)Σ*. We also give an application of this result.

This paper first proposes a new approach to designing high-quality, low-diameter, small mean-internode-distance (MID), k-subcubic-connected cyclic networks. The approach is a modification of the k-cubic-connected cyclic (k-ccc) network in which there are N=k2k-1 instead of N=k2k nodes in the k-ccc network. The special features of this network are: (1) It fills the gap between the number of nodes in k-ccc and (k+1)-ccc networks, but retains a constant number of link (3) per node in the network, (2) it allows higher quality, smaller diameters and mean internode distances hypercube networks with the same numbers of nodes. A second novel approach consists of a k+-sccc network with the same number of nodes as the k-ccc but with smaller diameters and mean internode distances. A generalized k-ccc network formed by nodes N=k2m is introduced for n-cube and k-ccc (modified or normal) networks that allows minimum network quality to be obtained where m may or may not equal to k. A routing algorithm for 4-sccc is also presented.

We present a novel replication technique for parallel applications where instances of the replicated application are active on different group of processors called replicas. The replication technique is based on the FTAG (Fault Tolerant Attribute Grammar) computation model. FTAG is a functional and attribute based model. The developed replication technique implements "active parallel replication," that is, all replicas are active and compute concurrently a different piece of the application parallel code. In our model replicas cooperate not only to detect and mask failures but also to perform parallel computation. The replication mechanisms are supported by FTAG run time system and are fully application-transparent. Different novel mechanisms for checkpointing and recovery are developed. In our model during rollback recovery only that part of the computation that was detected faulty is discarded. The replication technique takes full advantage of parallel computing to reduce overall computation time.

In this paper, we present an error concealment method to recover damaged blocks for block-based image coding schemes. Imperfect transmission of image data results in damaged blocks in the reconstructed images. Hence recovering damaged image blocks is needed for reliable image communications. To recover damaged blocks is to estimate damaged blocks from the correctly received or undamaged neighborhood information with a priori knowledge about natural images. The recovery problem considered in our method is to estimate a larger block, which consists of a damaged block and the undamaged neighborhood, from the undamaged neighborhood. To find an accurate estimate, a set of the feature vectors is introduced and an estimate is expressed as a linear combination of the feature vectors. The proposed method recoveres damaged blocks by projecting the undamaged neighborhood information onto the feature vectors. The sequential projections onto the feature vectors algorithm is proposed to find the projection coefficients of the feature vectors to minimize the squared difference of an estimate and the undamaged neighborhood information. We tested our algorithm through computer simulations. The experimental results showed the proposed method ourperforms the frequency domain prediction method in the PSNR values by 4.0-5.0dB. Tthe reconstructed images by the proposed method provide a good subjective quality as well as an objective one.

This paper proposes a new multiuser detector, quasi-decorrelating detector (QDD), for a synchronous CDMA system. The QDD has the same complexity as that of decorrelator detector (DD) although it uses feedback loops, the number of which is adjustable to balance the near-far resistance and noise enhancement. The results show that the QDD outperforms the DD under various operational conditions. The impact of different spreading codes on the performance of the QDD is studied. It is shown that the Gold code is the best spreading code suitable for the QDD.

This paper reports the thermal stability of particulate media, which include Co-Fe oxide, CrO2, and thick and thin MP tapes. By measuring the time decay of magnetization at room temperature, fluctuation fields were obtained as a function of reverse applied field. It was clarified that the fluctuation field has a constant and minimum value when the reverse applied field is equal to coercivity. Minimum fluctuation fields for the four particulate tapes were measured at several environmental temperatures ranging from -75 to +100. It was also clarified that the fluctuation field normalized by remanence coercivity increases as the environmental temperature increases for all tapes, indicating that it is a good measure of thermal stability. Activation volumes were also deduced as a function of temperature.

JUMP-1 is currently under development by seven Japanese universities to establish techniques for building an efficient distributed shared memory on a massively parallel processor. It provides a coherent cache with reduced hierarchical bit-map directory scheme to achieve cost effective and high performance management. Messages for coherent cache are transferred through a fat tree on the RDT (Recursive Diagonal Torus) interconnection network. RDT router supports versatile functions including multicast and acknowledge combining for the reduced hierarchical bit-map directory scheme. By using 0.5µm BiCMOS SOG technology, it can transfer all packets synchronized with a unique CPU clock (50MHz). Long coaxial cables (4m at maximum) are directly driven with the ECL interface of this chip. Using the dual port RAM, packet buffers allow to push and pull a flit of the packet simultaneously.

Advanced scientific and engineering problems require massively parallel computing. Critical to the designand ultimately the performanceof such computing systems is the interconnection network binding the computing elements, just as is the cardiovascular network to the human body. This paper develops a new interconnection network, "Tori connected mESHes (TESH)," consisting of k-ary n-cube connection of supernodes that comprise meshes of lower level nodes. Its key features are the following: it is hierarchical, thus allowing exploitation of computation locality as well as easy expansion (up to a million processors), and it appears to be well suited for 3-D VLSI implementation, for it requires far fewer number of vertical wires than almost all known multi-computer networks. Presented in the paper are the architecture of the new network, node addressing and message routing, 3-D VLSI/ULSI considerations, and application of the network to massively parallel computing. Specifically, we discuss the mapping on to the network of stack filtering, a hardware oriented technique for order statistic image filtering.

An implementation of photometric stereo is described in which all directions of illumination are close to and rotationally symmetric about the viewing direction. THis has practical value but gives rise to a problem that is numerically ill-conditioned. Ill-conditioning is overcome in two ways. First, many more than the theoretical minimum number of images are acquired. Second, principal components analysis (PCA) is used as a linear preprocessing technique to determine a reduced dimensionality subspace to use as input. The approach is empirical. The ability of a radial basis function (RBF) neural network to do non-parametric functional approximation is exploited. One network maps image irradiance to surface normal. A second network maps surface normal to image irradiance. The two networks are trained using samples from a calibration sphere. Comparison between the actual input and the inversely predicted input is used as a confidence estimate. Results on real data are demonstrated.

Microcellular radio direct-sequence code division multiple access (DC-CDMA) system using optical link to connect their base stations to a central station is a solution of cost-effective and efficient spectrum reuse to meet the growing demand for mobile communications. In addition to the inherent multiuser interference (MUI) of CDMA signals, the system capacity is significantly reduced by a nonlinear distortion (NLD) due to the nonlinearity of optical link. In this paper, a two-stage cancellation technique is introduced into the system to cancel both the MUI and the NLD. It is performed at the receiver of the central station where the random ingredients of all user signals are estimated, and the MUI and the NLD are rebuilt and removed from the received signal. The validity of the cancellation technique is theoretically analyzed and shown by the numerical results. The analytical method and its results are also applicable to other general nonlinear CDMA.

Recently, the spatio-temporal filter using linear analog Cellular Neural Network (CNN), called CNN filter array, has been proposed for the purpose of dynamic image processing. In this paper, we propose a design method of descrete-time cellular neural network filter which selectively extracts the particular moving object from other moving objects and noise. The CNN filter array forms a spatio-temporal filter by arranging cells with a same function. Each of these cells is a simple linear analog temporal filter whose input is the weighted sum of its neighborhood inputs and outputs and each cell corresponds to each pixel. The CNN filter is formed by new model of discrete time CNN, and the filter parameters are determined by applying backpropagation algorithm in place of the analytic method. Since the number of connections between neurons in the CNN-type filter is relatively few, the required computation in the learning phase is reasonable amount. Further, the output S/N ratio is improved by introducing nonlinear element. That is, if the ratio of output to imput is smaller than a certain value, the output signal is treated as a noise signal and ought to be rejected. Through some examples, it is shown that the target object is enhanced in the noisy environment.

In this paper, implementation of a first-order active complex filter with variable parameter using operational transconductance amplifiers (OTAs) and grounded copacitors is presented. The proposed configurations can be used as s key building block to realize high-order active complex filters with variable parameter in cascade and leapfrog configuration. Experimental results which are in good agreement with theoretical responses are also given o demonstrate the feasibility of the proposed configurations.

In order to improve luminance and luminous efficiency of color ac plasma displays (PDPs), absorption characteristics of ultraviolet rays were investigated for dielectric materials from a viewpoint of protecting layer of ac PDPs. The double protecting layer of MgF2 and MgO is clarified to be excellent property to improve the optical performance of color ac PDPs. The double protecting layer of MgF2 and MgO was applied to the barrier-rib electrode color ac PDPs and resulted in high luminance and luminous efficiency of 1030 cd/m2 and 1.0lm/W, respectively.

In this paper, a new trial for the signal processing is proposed along the same line as a previous study on the extended regression analysis based on the Bayes' theorem. This method enables us to estimate a response probability property of complicated systems in an actual case when observation values of the output response are roughly observed due to the quantization mechanism of measuring equipment. More concretely, the main purpose of this research is to find the statistics of the joint probability density function before a level quantization operation which reflects every proper correlation informations between the system input and the output fluctuations. Then, the output probability distribution for another kind of input is predicted by using the estimated regression relationship. Finally, the effectiveness of the proposed method is experimentally confirmed by applying it to the actually observed input-output data of the acoustic system.

In this paper, we prove that for a class of nonsymmetric neural networks with connection matrices T having nonnegative off-diagonal entries, -T is an M-matrix is a necessary and sufficient condition for absolute exponential stability of the network belonging to this class. While this result extends the existing one of absolute stability in Forti, et al., its proof given in this paper is simpler, which is completed by an approach different from one used in Forti, et al. The most significant consequence is that the class of nonsymmetric neural networks with connection matrices T satisfying -T is an M-matrix is the largest class of nonsymmetric neural networks that can be employed for embedding and solving optimization problem with global exponential rate of convergence to the optimal solution and without the risk of spurious responses. An illustrating numerical example is also given.

We give an explicit formula for the number of n-variable clique function in terms of the parameters based upon the numbers of intersecting antichains of the lower half of the n-cube. We present the numbers of clique functions with up to seven variables through computer evaluation of the parameters.

This paper describes a design technique of perfect reconstruction (PR) two-channel IIR filter bank. M.J.T. Smith et al., gave two types of PR IIR filter bank systems. One is the system such that the analysis and synthesis filters with nonlinear phase are implemented with all-pass polyphase filters and satisfy the power complementary condition approximately. The other is the system such that all the analysis and synthesis filters have liner phase responses and do not satisfy the power complementary condition. To improve coding performance, we propose a filter bank system such that all the analysis and synthesis filters have linear phase and satisfy the power complementary condition approximately.

Introducing a mathematical model of noise in stereo images, we propose a new criterion for intelligent statistical inference about the scene we are viewing by using the geometric information criterion (geometric AIC). Using synthetic and real-image experiments, we demonstrate that a robot can test whether or not the object is located very far away or the object is a planar surface without using any knowledge about the noise magnitude or any empirically adjustable thresholds.

In this letter, the absolute exponential stability result of neural networks with asymmetric connection matrices is obtained, which generalizes the existing one about absolute stability of neural networks, by a new proof approach. It is demonstrated that the network time constant is inversely proportional to the global exponential convergence rate of the network trajectories to the unique equilibrium. A numerical simulation example is also given to illustrate the obtained analysis results.

Obradovic and Parberry showed that any n-input k-ary function can be computed by a depth 4 unit-weight k-ary threshold circuit of size O(nkn). They also showed that any n-input k-ary symmetric function can be computed by a depth 6 unit-weight k-ary threshold circuit of size O(nk+1). In this paper, we improve upon and expand their results. The k-ary threshold circuits of nonunit weight and unit weight are considered. We show that any n-input k-ary function can be computed by a depth 2 k-ary threshold circuit of size O(kn-1). This means that depth 2 is optimal for computing some k-ary functions (e.g., a PARITY function). We also show that any n-input k-ary function can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn). Next, we show that any n-input k-ary symmetric function can be computed by a depth 3 k-ary threshold circuit of size O(nk-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(knk-1). Finally, we show that if the weights of the circuit are polynomially bounded, some k-ary symmetric functions cannot be computed by any depth 2 k-ary threshold circuit of polynomial-size.