A pseudoinverse rule, one of major rule to determine a weight matrix for associative memory, has large capacity comparing with other determining rules. However, it is wellknown that the rule has small domains of attraction of memory vectors on account of many spurious states. In this paper, we try to improve the problem by means of subtracting a constant from all diagonal elements of a weight matrix. By this method, many spurious states disappear and eigenvectors with negative eigenvalues are introduced for the orthocomplement of the subspace spanned by memory vectors. This method can be applied to two types of networks: binary network and analog network. Some computer simulations are performed for both two models. The results of the simulations show our improvement is effective to extend error correcting ability for both networks.

An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC1-reducible to REACHABILITY. That is, both of the problems belong to NC2. In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC1-reducible to REACHBILITY.

This paper discusses a new image resolution conversion method which converts not only spatial resolution but also amplitude resolution. This method involves considering impulse responses of image devices and human visual characteristics, and can preserve high image quality. This paper considers a system that digitizes the multilevel input image with high spatial resolution and low amplitude resolution using an image scanner, and outputs the image with low spatial resolution and high amplitude resolution on a CRT display. The algorithm thus reduces the number of pixels while increasing the number of brightness levels. Since a CRT display is chosen as the output device, the distribution of each spot in the display, which is modeled as a Gaussian function, is taken as the impulse response. The output image is then expressed as the summation of various amplitudes of the impulse response. Furthermore, human visual perception, which bears a nonlinear relationship to the spatial frequency component, is simplified and modeled with a cascade combination of low-pass and high-pass filters. The output amplitude is determined so that the error between the output image and the input image, after passing through the visual perception filter, is minimized. According to the results of a simulation, it is shown that image quality can be largely preserved by the proposed method, while significant image information is lost by conventional methods.

Distributed algorithms that entail successive rounds of message exchange are called decentralized consensus protocols. Several consensus protocols use a finite projective plane as a communication structure and require 4nn messages in two rounds, where n is the number of nodes. This paper presents an efficient communication structure that uses a finite projective plane with a duality of indices. The communication structure requires 2nn messages in two rounds, and can therefore halve the number of messages. It is shown that a finite projective plane with a duality can be constructed from a difference set, and that the presented communication structure has two kinds of symmetry.

We developed an automatic data processing algorithm for a ground-probing radar which is essential in analyzing a large amount of data by a non-expert. Its aim is to obtain an optimum result that the conventional technique can give, without the assistance of an experienced operator. The algorithm is general except that it postulates the existence of at least one isolated target in the radar image. The raw images of underground objects are compressed in the vertical and the horizontal directions by using a pulse-compression filter and the aperture synthesis technique, respectively. The test function needed to configure the compression filter is automatically selected from the given image. The sensitivity of the compression filter is adjusted to minimize the magnitude of spurious responses. The propagation velocity needed to perform the aperture synthesis is determined by fitting a hyperbola to the selected echo trace. We verified the algorithm by applying it to the data obtained at two test sites with different magnitude of clutter echoes.

A design of an Ada IPC (Inter-Program Communication) interface is proposed, through which a designer of distributed systems can (a) specify arbitrary data types needed for inter-program communication and (b) use parallel programming features to build highly parallel systems; a test simulator was built for execution of the IPC interface and a multi-window system was realized as an application of the interface on the simulator; the interface was found to be useful, making description of inter-program communication simpler and easier.

Truncated sum (TSUM for short) is useful for MV-PLA's realization. This paper introduces a new class of multiple-valued logic functions that are expressed by truncated sum, differential product (DPRODUCT for short), NOT and variables, where TSUM (x, y)min (xy, p1) and DPRODUCT (x, y)max (xy(p1), 0) is newly defined as the product that is derived by applying De Morgan's laws to TSUM. We call the functions T-functios. First, this paper clarifies that a set of T-functions is not a lattice. It clarifies that Lukasiewicz implication can be expressed by TSUM and NOT. It guarantees that a set of p-valued T-functios is not complete but complete with constants. Next, the speculations of the number of T-functions for less than ten radixes are derived. For eleven or more radix p, a speculation of the number of p-valued T-functions is shown. Moreover, it compares the T-functions with B-functions. The B-functions have been defined as the functions expressed by MAX, MIN, NOT and variables. As a result, it shows that a set of T-functions includes a set of B-functions. Finally, an inclusion relation among these functional sets and normality condition is shown.

J. Bresnan and R. M. Kaplan introduced lexical-functional grammars (LFGs, for short) as a new formalism for human language syntax. It is important to show formal properties of this kind of grammars in order to characterize the formal complexity of human languages. In this paper, we will show that the emptiness problem for LFGs is undecidable.

This paper advocates the use of linear objective function in analytic analog placement. The role of linear and quadratic objctive functions in the behavior and results of an analog placement algorithm based on the force directed method is discussed. Experimental results for a MCNC benchmark circuit and another one from text books are shown to demonstrate the effect of a linear and a quadratic objective function on the analog constraint satisfaction and CPU time. By introducing linear objective function to the algorithm, we obtain better placements in terms of analog constraint satisfaction and computation cost than in case of conventional quadratic objective function.

A problem which often arises in computer vision is that of matching corresponding points of images. In the case of object recognition, for example, the computer compares new images to templates from a library of known objects. A common way to perform this comparison is to extract feature points from the images and compare these points with the template points. Another common example is the case of motion detection, where feature points of a video image are compared to those of the previous frame. Note that in both of these example, the point correspondence is complicated by the fact that the point sets are not only randomly ordered but have also been distorted by an unknown transformation and having quite different coordinates. In the case of object recognition, there exists a transformation from the object being viewed, to its projection onto the camera's imaging plane, while in the motion detection case, this transformation represents the motion (translation and rotation) of the ofject. If the parameters of the transformation are completely unknow, then all n! permutations must be compared (n : number of feature points). For each permutation, the ensuing transformation is computed using the least-squared projection method. The exponentially large computation required for this is prohibitive. A neural computational method is propopsed to solve these combinatorial problems. This method obtains the best correspondence matching and also finds the associated transform parameters. The method was applied to two dimensional point correspondence and three-to-two dimensional correspondence. Finally, this connectionist approach extends readily to a Boltzmann machine implementation. This implementation is desirable when the transformation is unknown, as it is less sensitive to local minima regardless of initial conditions.

Recent developments and case studies regarding VLSI device chip failure analysis are reviewed. The key failure analysis techniques reviewed include EMMS (emission microscopy), OBIC (optical beam induced current), LCM (liquid crystal method), EBP (electron beam probing), and FIB (focused ion beam method). Further, future possibilities in failure analysis, and some promising new tools are introduced.

This paper uses both network analysis and experiments to confirm that the neural network learning algorithm that minimizes output variation (BPV) provides much more robustness than back-propagation (BP) or BP with noise-modified training samples (BPN). Network analysis clarifies the relationship between sample displacement and what and how the network learns. Sample displacement generates variation in the output of the output units in the output layer. The output variation model introduces two types of deformation error, both of which modify the mean square error. We propose a new error which combines the two types of deformation error. The network analysis using this new error considers that BPV learns two types of training samples where the modification is either towards or away from the category mean, which is defined as the center of sample distribution. The magnitude of modification depends on the position of the training sample in the sample distribution and the degree of leaning completion. The conclusions is that BPV learns samples modified towards to the category mean more stronger than those modified away from the category mean, namely it achieves nonuniform learning. Another conclusion is that BPN learns from uniformly modified samples. The conjecture that BPV is much more robust than the other two algorithms is made. Experiments that evaluate robustness are performed from two kinds of viewpoints: overall robustness and specific robustness. Benchmark studies using distorted handprinted Kanji character patterns examine overall robustness and two specifically modified samples (noise-modified samples and directionally-modified samples) examine specific robustness. Both sets of studies confirm the superiority of BPV and the accuracy of the conjecture.

The Alopex algorithm is presented as a universal learning algorithm for neural networks. Alopex is a stochastic parallel process which has been previously applied in the theory of perception. It has also been applied to several nonlinear optimization problems such as the Travelling Salesman Problem. It estimates the weight changes by using only a scalar cost function which is measure of global performance. In this paper we describe the use of Alopex algorithm for solving nonlinear learning tasks by multilayer feed-forward networks. Alopex has several advantages such as, ability to escape from local minima, rapid algorithmic computation based on a scalar cost function and synchronous updation of weights. We present the results of computer simulations for several tasks, such as learning of parity, encoder problems and the MONK's problems. The learning performance as well as the generalization capacity of the Alopex algorithm are compared with those of the backpropagation procedure, and it is shown that the Alopex has specific advantages over backpropagation. An important advantage of the Alopex algorithm is its ability to extract information from noisy data. We investigate the efficacy of the algorithm for faster convergence by considering different error functions. We show that an information theoretic error measure shows better convergence characteristics. The algorithm has also been applied to more complex practical problems such as undersea target recognition from sonar returns and adaptive control of dynamical systems and the results are discussed.

From a practical point of view, a cryptosystem should require a small key size and less running time. For this purpose, we often select its definition field in such a way that the arithmetic can be implemented fast. But it often brings attacks which depend on the definition field. In this paper, we investigate the definition field Fp on which elliptic curve cryptosystems can be implemented fast, while maintaining the security. The expected running time on a general construction of many elliptic curves with a given number of rational points is also discussed.

This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), which is optimal since Ω(nk) line segments are included there. The algorithm can sweep the at-most-k levels of the arrangement using O(n) space. Although Everett et al. recently gave an algorithm for constructing the at-most-k levels with the same time complexity independently, our algorithm is superior with respect to the space complexity as a sweep algorithm. Then, we apply the algorithm to a bipartitioning problem of a bichromatic point set： For r red points and b blue points in the plane and a directed line L, the figure of demerit fd(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.

The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows： Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.

This paper investigates the accepting powers of one-way alternating multi-stack-counter automata (lamsca's) and one-way alternating multi-counter automata (lamsca's) which operate in realtime. For each k1, let 1ASCA (k, real) (1ACA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stach-counter (k-counter) automata, and let 1USCA(k, real)(1UCA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stack-counter (k-counter) automata with only universal states. We first investigate a relationship between the accepting powers of realtime lamsca's (lamca's) with only universal states, with only existential states, and with full alternation. We then investigate hierarchical properties based on the numbers of counters and stackcounters, and show, for example, that for each k1, 1USCA(k+1, real)-1ASCA(k, real)φ and 1UCA(k+1, real)-1ACA(k, real)φ. We finally investigate a relationship between the accepting powers of realtime lamsca's and lamca's, and show, for example, that there are no i and j such that 1UCA(i, real)=1USCA(j, real), and 1USCA(k, real)-1ACA(k, real)φ for each k1.

An extension of the notion of cryptographically strong pseudo-random generator to a distributed setting is proposed in this paper. Instead of a deterministic function to generate a pseudo-random bit string from a truly random shorter string, we have a deterministic secure protocol for a group of separate entities to compute a secretly shared pseudo-random string from a secretly shared and truly random shorter string. We propose a precise definition of this notion in terms of Yao's computational entropy and describe a concrete construction using Shamir's pseudo-random number generator. Several practical applications are also discussed.

In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by 1 in the protocol. These results suggest that, even when all channeles in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the channel capacity 0 does not allow protocols to transmit and recieve messages.

A new regularization cost function for generalization in real-valued function learning is proposed. This cost function is derived from the maximum likelihood method using a modified sample distribution, and consists of a sum of square errors and a stabilizer which is a function of integrated square derivatives. Each of the regularization parameters which gives the minimum estimation error can be obtained uniquely and non-empirically. The parameters are not constants and change in value during learning. Numerical simulation shows that this cost function predicts the true error accurately and is effective in neural network learning.