We show that the permanent of an m n rectangular matrix can be computed with O(n 2m 3m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log3 2 and n .

Auctions are a critical element of the electronic commerce infrastructure. But for real-time applications, auctions are a potential problem - they can cause significant time delays. Thus, for most real-time applications, sealed-bid auctions are recommended. But how do we handle tie-breaking in sealed-bid auctions? This paper analyzes the use of multi-round auctions where the winners from an auction round participate in a subsequent tie-breaking second auction round. We perform this analysis over the classical first-price sealed-bid auction that has been modified to provide full anonymity. We analyze the expected number of rounds and optimal values to minimize communication costs.

Computational sensor (smart sensor, vision chip in other words) is a very small integrated system, in which processing and sensing are unified on a single VLSI chip. It is designed for a specific targeted application. Research activities of computational sensor are described in this paper. There have been quite a few proposals and implementations in computational sensors. Firstly, their approaches are summarized from several points of view, such as advantage vs. disadvantage, neural vs. functional, architecture, analog vs. digital, local vs. global processing, imaging vs. processing, new processing paradigms. Then, several examples are introduced which are spatial processings, temporal processings, A/D conversions, programmable computational sensors. Finally, the paper is concluded.

We have proposed an algorithm to apply perfectly matched layer (PML) absorbing boundary condition to the noncubic cell time-domain method. The extended method has a merit of flexibility in truncating the computational domain by the use of a curvilinear PML. In this paper we apply a circular PML for computing the scattered fields of a dielectric cylinder or cylindrical shell of arbitrary cross section shape. Numerical results are presented to demonstrate the accuracy of this method.

This paper formulates problems of fitting two corresponding sets of points by translation, rotation and scaling, and proposes efficient algorithms for the fitting. The algorithms are based on the theory of lower envelopes, or Davenport-Schinzel sequences, and linearization techniques in computational geometry, and are related to dynamic furthest Voronoi diagrams.

This paper is concerned with the validation of simple turning points of two-point boundary value problems of nonlinear ordinary differential equations. Usually it is hard to validate approximate solutions of turning points numerically because of it's singularity. In this paper, it is pointed out that applying the infinite dimensional Krawcyzk-based interval validation method to enlarged system, the existence of simple turning points can be verified. Taking an example, the result of validation is also presented.

This paper is concerned with a concept called universality or completeness of sets of logic devices. Universality characterizes sets of logic devices which can be used for the construction of arbitrary logic circuits. The elemental universality proposed here is the most general condition of universality which covers logic devices with/without delay time and combinational/sequential circuits. The necessary and sufficient condition of elemental universality shows that nonlinearity and nonmonotonicity are essential conditions for the realization of various digital mechanisms.

Hogg and Huberman have proposed a strategy for stabilizing chaotic multi-agent systems. This paper applies their strategy to a resource allocation problem in a manufacturing system consisting of two machines and two types of parts. These part-types conflict each other over resource allocation. We introduce a discrete-time model of the system by using game theory, and examine stability and bifurcation phenomena of its fixed point. We show by computer simulation that chaotic behaviors are observed after successive occurrence of period-doubling bifurcations. It is also shown that the optimal state of the system is stabilized by a reward mechanism.

This paper proposes an automatic structural programming system. Genetic Programming achieves success for automatic programming using the evolutionary process. However, the approach doesn't deal with the essential program concept in the sense of what is called a program in software science. It is useful that a program be structured by various sub-structures, i. e. subroutines, however, the above-mentioned approach treats a single program as one sequence. As a result of the above problem, there is a lack of reusability, flexibility, and a decreases in the possibility of use as a utilitarian programming system. In order to realize a structural programming system, this paper proposes a method which can generate a program constructed by subroutines, named formula, using the evolutionary process.

The adaptive associative memory proposed by Ma is used to construct a new model of semantic network, referred to as associative semantic memory (ASM). The main novelty is its computational effectiveness which is an important issue in knowledge representation; the ASM can do inference based on large conceptual hierarchies extremely fast-in time that does not increase with the size of conceptual hierarchies. This performance cannot be realized by any existing systems. In addition, ASM has a simple and easily understandable architecture and is flexible in the sense that modifying knowledge can easily be done using one-shot relearning and the generalization of knowledge is a basic system property. Theoretical analyses are given in general case to guarantee that ASM can flawlessly infer via pattern segmentation and recovery which are the two basic functions that the adaptive associative memory has.

In [1], approximate eigenvalues and eigenvectors are defined and algorithms to compute them are described. However, the algorithms require a certain condition: the eigenvalues of M modulo S are all distinct, where M is a given matrix with polynomial entries and S is a maximal ideal generated by the indeterminate in M. In this paper, we deal with the construction of approximate eigenvalues and eigenvectors when the condition is not satisfied. In this case, powers of approximate eigenvalues and eigenvectors become, in general, fractions. In other words, approximate eigenvalues and eigenvectors are expressed in the form of Puiseux series. We focus on a matrix with univariate polynomial entries and give complete algorithms to compute the approximate eigenvalues and eigenvectors of the matrix.

Two-dimensional (2-D) adaptive digital filters (ADFs) for 2-D signal processing have become a fascinating area of the adaptive signal processing. However, conventional 2-D FIR ADF's require a lot of computations. For example, the TDLMS requires 2N2 multiplications per pixel. We propose a new 2-D adaptive filter using the FFTs. The proposed adaptive filter carries out the fast convolution using overlap-save method, and has parallel structure. Thus, we can reduce the computational complexity to O(log2N) per pixel.

Topological Walk is an algorithm that can sweep an arrangement of n lines in O(n2) time and O(n) space. This paper revisits Topological Walk to give its new interpretation in contrast with Topological Sweep. We also survey applications of Topological Walk to make the distinction clearer.

This correspondence reports novel computationally efficient algorithms for multiplication of bicomplex numbers, which belong to hypercomplex numbers. The proposed algorithms require less number of real multiplications than existing methods. Furthermore, they give more effective implementation when applied to constant coefficient digital filters.

Though causal order of message delivery simplifies the design and development of distributed applications, the overhead of enforcing it is not negligible. We claim that a causal order algorithm which does not send any redundant information is efficient in the sense of communication overhead. We characterize and classify the redundant information into four categories: information regarding just delivered, already delivered, just replaced, and already replaced messages. We propose an efficient causal multicast algorithm which prevents propagation of these redundant information. Our algorithm sends less amount of control information needed to ensure causal order than other existing algorithms and can also be applied to systems whose communication channels are not FIFO. Since our algorithm's communication overhead increases relatively slowly as the number of processes increases, it shows good scalability feature. The potential of our algorithm is shown by simulation study.

Recently, two new efficient server-aided RSA secret computation protocols were proposed. They are efficient and can guard against some active attacks. In this letter, we propose two multi-round active attacks which can effectively reduce their security level even break them.

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.

This paper focuses on recovering from processor transient faults in pipelined multiprocessor systems. A pipelined machine may employ out of order execution and branch prediction techniques to increase performance, thus a precise computation state would not be available. We propose an efficient scheme to maintain the precise computation state in a pipelined machine. The goal of this paper is to implement checkpointing and rollback recovery utilizing the technique of precise interrupt in a pipelined system. Detailed analysis is included to demonstrate the effectiveness of this method.

This paper describes cellular spaces (or cellular automata) with capabilities of parallel self-reproduction and of parallel universal simulation of other cellular spaces. It is shown that there is a 1-dimensional cellular space U, called a parallel universal simulator, that can simulate any given 1-dimensional cellular space S in the sense that if an initial configuration of U has a coded information of both the local function and an initial configuration of S, then U has the same computation result that S has and the computation time of U is proportional to that of S. Two models of nontrivial parallel self-reproduction are also shown. One model is based on "state-exchange" method, and the other is based on a fixed point program of the parallel universal simulator.

Some kind of practical problems such as security verification of cryptographic protocols can be described as a problem to accomplish a given purpose by using limited operations and limited materials only. To model such problems in a natural way, unification problems under constrained substitutions have been proposed. This paper is a collection of results on the decidability and the computational complexity of a syntactic unification problem under constrained substitutions. A number of decidable, undecidable, tractable and intractable results of the problem are presented. Since a unification problem under constrained substitutions can be regarded as an order-sorted unification problem with term declarations such that the number of sorts is only one, the results presented in this paper also indicate how the intractability of order-sorted unification problems is reduced by restecting the number of sorts to one.