Ordered Binary Decision Diagrams (OBDDs) are graph-based representations of Boolean functions which are widely used because of their good properties. In this paper, we introduce nondeterministic OBDDs (NOBDDs) and their restricted forms, and evaluate their expressive power. In some applications of OBDDs, canonicity, which is one of the good properties of OBDDs, is not necessary. In such cases, we can reduce the required amount of storage by using OBDDs in some non-canonical form. A class of NOBDDs can be used as a non-canonical form of OBDDs. In this paper, we focus on two particular methods which can be regarded as using restricted forms of NOBDDs. Our aim is to show how the size of OBDDs can be reduced in such forms from theoretical point of view. Firstly, we consider a method to solve satisfiability problem of combinational circuits using the structure of circuits as a key to reduce the NOBDD size. We show that the NOBDD size is related to the cutwidth of circuits. Secondly, we analyze methods that use OBDDs to represent Boolean functions as sets of product terms. We show that the class of functions treated feasibly in this representation strictly contains that in OBDDs and contained by that in NOBDDs.

A large scale simulation for polymer chains in good solvent is performed. The implementation technique for efficient parallel execution, optimization, and load-balancing are discussed on this practical application. Finally, a simple performance model is proposed.

In this paper, we introduce a computational mode of a tree transducer called a bi-stage transducer and study its properties. We consider a mapping on trees realized by composition of any sequence of top-down transducers and bottom-up transducers, and call such a mapping a multi-phase tree transformation. We think a multi-phase tree transformation is sufficiently powerful. It is shown that in the case of rank-preserving transducers, a multi-phase tree transformation is realized by a bi-stage transducer.

In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions ui(I) on I, and define an optimization problem of finding the interval I maximizing f(I) subject to ui(I) > Ki for given real numbers Ki (i = 1, 2, , h). We propose efficient alogorithms to solve the above optimization problem if the objective function is either additive or quotient, and the conditional functions are additive, where a function f is additive if f(I) = ΣiIf^(i) extending a function f^ on U, and quotient if it is represented as a quotient of two additive functions. We use computational-geometric methods such as convex hull, range searching, and multidimensional divide-and-conquer.

Compressible viscous flows past a space plane have been elucidated by parallel computation on the NWT. The NWT is a vector-parallel architecture computer system which achieves remarkably high performance in processing speed and memory storage. We have examined the advantages of the NWT in order to simulate realistic flow problems in engineering, such as the investigation of global and local aerodynamic characteristics of a space plane. The accuracy of the computational results has been verified by comparison with experimental data. The simplified domain-decomposition technique introduced here is easy to apply for parallel implementation to significantly improve the acceleration rate of computations. The larger available memory storage enables us to conduct a grid refinement study through which several points concerning CFD simulation of a space plane are obtained.

We show that the truth of a prenex normal form Presburger sentence bounded only by existential quantifiers (or an EPP-sentence) involving two variables can be decided in deterministic polynomial time. Specifically, an upper bound of the computation for the decision is O(n3u), where n is the number of atoms of the EPP-sentence, and u is the largest absolute value of all coefficients in the EPP-sentence. In the analysis for the upper bound, the random access machine is assumed for the machine model. Additionally, a uniform cost criterion is assumed. Deciding the truth of an EPP-sentence is an NP-complete problem, when the number of variables is not fixed. Furthermore, whether the truth of an EPP-sentence involving two or more variables can be decided in deterministic polynomial time, when the number of variables is fixed, or not has remained an open problem. We previously proposed a procedure for quickly deciding the truth of an EPP-sentence on the basis of a suggestion by D.C.Cooper. We found the upper bound by analyzing the decision procedure. The procedure can be applied to both automated correctness proof of specification in various design fields and detection of infeasible paths in a program. In the procedure, a matrix denoting coefficients of the variables in the EPP-sentence is triangulated.

This paper presents algorithms for computing the Minkowski sum of two polygons P and Q for a family of problems. For P being convex and Q being monotone, an algorithm is given with O (nm) time and space complexity. For both P and Q being monotone polygons, an O (nm log nm) time algorithm is presented and it is shown that the complexity of the sum is Θ (nmα(min(n,m))) in the worst case, where α() is the inverse of Ackermann's function. Finally, an O ((nm+k)log nm) time complexity algorithm is given when P is monotone and Q is simple, where k in the worst case could be Θ(n2m). The complexity of P Q is shown to be Θ(n2m) in the worst case. Here, m and n denote the number of edges of P and Q, respectively.

In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2clog n)/c), for all 1c [log(n+1)]-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks[5], we also show an Ω (log n/log log n) lower bound for the depth of the threshold circuits. This is an answer to the open question posed in [11].

In this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number δ > 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most δ under the condition that any translation and rotation can be applied to P. Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(n8), O((n7/k3) polylog(n)) and O(n4) respectively, where n denotes the size of larger input structure and k denotes the minimum size of the alignment to be obtained. All of these have the following common framework: a series of initial superpositions are computed; for each of such superpositions, a rough alignment is first computed using a dynamic programming technique, and then it is refined through an iterative improvement procedure which also uses dynamic programming; the best alignment among them is selected as an output. The difference among three algorithms lies in the methods of finding initial superpositions. BASICALIGN, RANDALIGN and FRAGALIGN use exhaustive search, random sampling technique and fragment-based search, respectively. We prove guaranteed approximation ratios (in the sense of distances between point pairs) for theoretical versions of BASICALIGN and RANDALIGN. Practical versions of RANDALIGN and FRAGALIGN were implemented and compared with a previous algorithm using real protein structure data. The experimental results show that FRAGALIGN is best among them and it outputs good alignments quickly.

For reduction of computational complexity in the IA algorithm, the thinned-out IA algorithm in which only one step size is updated every iteration is proposed and is complementarily switched with the HA algorithm according to the convergence. The switching is determined by using the gradient of the error signal power. These are investigated through the computer simulations.

Analog computation is a processing method that solves problems utilizing an analogy of a physical system to the problem. As it is based on actual physical effects and not on symbolic operations, it is therefore a promising architecture for quantum processors. This paper presents an idea for relating quantum structures with analog computation. As an instance, a method is proposed for solving an NP-complete (nondeterminis-tic polynomial time complete) problem, the three-color-map problem, by using a quantum-cell circuit. The computing process is parallel and instantaneous, so making it possible to obtain the solution in a short time regardless of the size of the problem.

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.

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.

A simple algorithm is proposed for representing nonseparable functions by equivalent separable functions. In this algorithm, functions are first represented by computational graphs, which are directed graphs representing the computational process of the functions. Then, the vertices of the computational graphs are searched in preorder or postorder, and the transformation to separable forms is performed at the places where it is necessary. By this repetition of the transformation, nonseparable functions are represented by separable functions automatically. The proposed algorithm will be useful in various fields of science and engineering because funcutions of one variable are easy to deal with.

The problem of genetic algorithm's efficiency has been attracting the attention of genetic algorithm community. Over the last decade, considerable researches have focused on improving genetic algorithm's performance. However, they are generally under the framework of natural evolutionary mechanism and the major genetic operators, crossover and mutation, are activated by the prior probabilities. An operator based on a prior probability possesses randomness, that is, the unexpected individuals are frequently operated, but the expected individuals are sometimes not operated. Moreover, as the evaluation function is the link between the genetic algorithm and the problem to be solved, the evaluation function provides the heuristic information for evolutionary search. Therefore, how to use this kind of heuristic information (present and past) is influential in the efficiency of evolutionary search. This paper, as an attempt, presents a eugenics-based genetic algorithm (EGA) -- a genetic algorithm that reflects the human's decision will (eugenics), and fully utilizes the heuristic information provided by the evaluation function for the decisions. In other words, EGA = evolutionary mechanisms + human's decision will + heuristic information. In EGA, the ideas of the positive eugenics and the negative eugenics are applied as the principle of selections and the selections are not activated by the prior probabilities but by the evaluation values of individuals. A method of genealogical chain-based selection for mutation is proposed, which avoids the blindness of stochastic mutation and the disruptive problem of mutation. A control strategy of reasonable competitions is proposed, which brings the effects of crossover and mutation into full play. Three examples, the minimum problem of a standard optimizing function--De Jong's test function F2, a typical combinatorial optimization problem--the traveling salesman problem, and a problem of identifying nonlinear system, are given to show the good performance of EGA.

Processor networks connected by buses have attracted considerable attention. Since a reconfigurable array is more powerful than a PRAM and more practical, it becomes the focus of attention. The Processor Array with Reconfigurable Bus System (PARBS) and the Reconfigurable Multiple Bus Machine (RMBM) are both models of parallel computation based on reconfigurable bus and processor array. The PARBS is a processor array that consists of processors arranged to a 2-dimensional grid with a reconfigurable bus system. The RMBM is also made of processors and reconfigurable bus system, but the processors are located in a row and the number of processors and the number of buses are independent of each other. Four versions of RMBM has been proposed and Extended RMBM (E-RMBM) is regarded as the most powerful one among them. In this paper, we describe that a PARBS of size N M can be simulated in constant time by a E-RMBM of 4NM processors, M + 3 buses and 1 read buffer, and that a E-RMBM of P processors, B buses and D read buffers can be also simulated in constant time by a PARBS of size B P. A PARBS or RMBM that solves a computational problem of size n is polynomially bounded iff the product of the number of processors and buses and red and write ports is O (nc), for some constant c. When a PARBS is polynomially bounded, the E-RMBM which simulates it is also polynomially bounded, and vice versa.

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.

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.

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.

GDL is the language whose membership problerm is polynomial-time Turing equivalent to the discrete logarithm problem for a general finite group G. This paper gives a characterization of GDL from the viewpoint of computational complexity theory. It is shown that GDL NP co-AM, assuming that G is in NP co-NP, and that the group law operation of G can be executed in polynomial time of the element size. Furthermore, as a natural probabilistic extension, the complexity of GDL is investigated under the assumption that the group law operation is executed in an expected polynomial time of the element size. In this case, it is shown that GDL MA co-AM if G MA co-MA. As a consequence, we show that GDL is not NP-complete unless the polynomial time hierarchy collapses to the second level.