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 u_i(I) on I, and define an optimization problem of finding the interval I maximizing f(I) subject to u_i(I) > K_i for given real numbers K_i (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.

The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n² processors on a CRCW PRAM. The second one is deterministic and runs in O(log ²n) timeusing n⁴ processors on an EREW PRAM. The last one is deterministic and runs in O(log ⁵n) time using n³ processors on an EREW PRAM. The results put the problem in the class NC.

Topological sorting is, given with a directed acyclic graph G = (V, E), to find a total ordering of the vertices such that if (u, v) E then u is ordered before v. Instead of finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

This paper discusses the largest common similar substructure (in short, LCSS) problem for trees. The problem is, for all pairs of "substructure of A and that of B," to find one of them, denoted by A and B', such that A is most similar to B' and the sum of the number of vertices of A and that of B' is largest. An algorithm for the LCSS problem for unrooted and unordered trees (in short, trees) and that for trees embedded in a plane (in short, Co-trees) are proposed. The time complexity of the algorithm for trees is O (max (m_a, m_b)² N_aN_b) and that for CO-trees is O (m_am_bN_aN_b), where, m_a (m_b) and N_a (N_b) are the largest degree of a vertex of tree T_a (T_b) and the number of vertices of T_a (T_b), respectively. It is easy to modify the algorithms for enumerating all of the LCSSs for trees and CO-trees. The algorithms can be applied to structure-activity studies in chemistry and various structure comparison problems.

In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.

We describe our implementation of the Hypercube variation of the Multiple Polynomial Quadratic Sieve (HMPQS) integer factorization algorithm on a Parsytec GC computer with 128 processors. HMPQS is a variation on the Quadratic Sieve (QS) algorithm which inspects many quadratic polynomials looking for quadratic residues with small prime factors. The polynomials are organized as the nodes of an n-dimensional cube. We report on the performance of our implementations on factoring several large numbers for the Cunningham Project.

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 factorization method for a string polynomial called the constant method is proposed. This uses essentially three operations; classification of monomials, gcrd (greatest common right divisor), and lcrm (least common rigth multiple). This method can be applied to string polynomials except that their constants cannot be reduced to zeros by the linear transformation of variables. To factorize such excluded string polynomials, the naive method is also presented, which computes simply coefficients of two factors of a given polynomial, but is not efficient.

This paper proposes a unified approach by means of the binary decision diagram, BDD in short, to solve #P-hand problems of counting the number of paths between two terminals in undirected and directed graphs. Our approach provides algorithms running in O (2^{O (n)} ) time for typical planar graphs such as grid graphs. In fact, for any class of graphs having a good elimination ordering, this paradigm provides efficient solutions.

The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.

This paper proposes a new method for recovering the original signals from their linear mixtures observed by the same number of sensors. It is performed by identifying the linear transform from the sources to the sensors, only using the sensor signals. The only assumption of the source signals is basically the fact that they are statistically mutually independent. In order to perform the 'blind' identification, some time-correlational information in the observed signals are utilized. The most important feature of the method is that the full information of available time-correlation data (second-order statistics) is evaluated, as opposed to the conventional methods. To this end, an information-theoretic cost function is introduced, and the unknown linear transform is found by minimizing it. The propsed method gives a more stable solution than the conventional methods.

In this paper,we propose general fast one dimensional (1-D) and two dimensional (2-D) slant transform algorithms. By introducing simple and structural permutations, the heavily computational operations are centralized to become standardized and localized processing units. The total numbers of multiplications for the proposed fast 1-D and 2-D slant transforms are less than those of the existed methods. With advantages of convenient description in formulation and efficient computation for realization, the proposed fast slant transforms are suitable for applications in signal compression and pattern recognition.

In this paper, we present a novel way to design biorthogonal and paraunitary linear phase filter banks. The square error of the perfect reconstruction of the filter bank is expressed in quadratic form of filter coefficients and the cost function is minimized by solving linear equation iteratively without nonlinear optimization. With some modifications, this method is extended to the design of paraunitary filter banks. Furthermore, the lattice structure of odd-channel paraunitary filter banks is also derived. Design examples are given to validate the proposed method.

It is shown that two-dimensional linear phase FIR digital filters with various shapes of frequency response can be designed and realized as modular array structures free of multiplier coefficients. The design can be performed by judicious selection of two low order linear phase transfer functions to be used at each module as kernel filters. Regular interconnection of the modules in L rows and K columns conditioned with boundary coefficients 1, 0 and 1/2 results in higher order digital filters. The kernels should be chosen appropriately to, first, generate the desired shape of frequency response characteristic and, second, lend themselves to multiplierless realization. When these two requirements are satisfied, the frequency response can be refined to possess narrower transition bands by adding additional rows and columns. General properties of the frequency response of the array are investigated resulting in Theorems that serve as valuable tools towards appropriate selection of the kernels. Several design examples are given. The array structures enjoy several favorable features. Specifically, regularity and lack of multiplier coefficients makes it suitable for high-speed systolic VLSI implementation. Computational complexity of the structure is also studied.

In the adaptive lattice estimation process, it is well known that the convergence speed of the successive stage is affected by the estimation errors of reflection coefficients in its preceding stages. In this paper, we propose block estimation methods of two-dimensional (2-D) adaptive lattice filter. The convergence speed of the proposed algorithm is significantly enhanced by improving the adaptive performance of preceding stages. Furthermore, this process can be simply realized. The modeling of 2-D AR field and texture image are demonstrated through computer simulations.

The numerical properties of the recursive least squares (RLS) algorithm and its fast versions have been extensively studied. However, very few investigations are reported concerning the numerical behavior of the predictor based least squares (PLS) algorithms that provide the same least squares solutions as the RLS algorithm. This paper presents a comparative study on the numerical performances of the RLS and the backward PLS (BPLS) algorithms. Theoretical analysis of three main instability sources reported in the literature, including the overrange of the conversion factor, the loss of symmetry and the loss of positive definiteness of the inverse correlation matrix, has been done under a finite-precision arithmetic. Simulation results have confirmed the validity of our analysis. The results show that three main instability sources encountered in the RLS algorithm do not exist in the BPLS algorithm. Consequently, the BPLS algorithm provides a much more stable and robust numerical performance compared with the RLS algorithm.

We extend the Rabin cryptosystem to the Eisenstein and Gauss fields. Methods for constructing the complete representation class and modulo operation of the ideal are presented. Based on these, we describe the methods of encryption and decryption. This proposed cryptosystem is shown to be as intractable as factorization, and recently presented low exponent attacks do not work against it.

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.

An alternative defuzzification technique for center of gravity calculation is proposed. The technique allows evaluation of fuzzy inferences without the use of multiplication. In fuzzy logic controllers with many outputs, the proposed scheme reduces the circuit complexity compared with other implementations.

A new method to obtain the coefficients of Daubechies's scaling functions is given, in which it is not necessary to find the complex zeros of polynomials. Consequently it becomes easier to obtain the coefficients of arbitrary order from 2 to 40 with high accuracy.

A method of planar curve classification, which is invariant to rotation, scaling and translation using the zerocrossings representation of wavelet transform was introduced. The description of the object is represented by taking a ratio between its two adjacent boundary points so it is invariant to object rotation, translation and size. Transforming this signal to zero-crossings representation using wavelet transform, the minimum distance between the object and model while shifting the signals each other, can be used as classification parameter.

We frequently use a polynomial to approximate a complex function. This study shows a method which determines the optimum coefficients and the number of terms of the polynomial, and the error of the polynomial is estimated.

This paper deals with an orthogonal functional expansion of a non-linear stochastic functional of a stationary binary sequence taking 1 with equal probability. Several mathematical formulas, such as multi-variate orthogonal polynomials, recurrence formula and generating function, are given in explicit form. A simple example of orthogonal functional expansion and stationary random seqence generated by the stationary binary sequence are discussed.

A modified error correction/detection scheme based on the scheme by Yi and Lee is proposed. Algebraic decoding is used to perform error correction. Error detection is performed by an absolute value test. It is shown that the proposed scheme bridges the performance gap between Yi and Lee's scheme and Forney's optimal scheme.

In this paper, a new method capable of effectively coding arbitrarity-shaped image regions is presented. The image region is spanned into the 8 8 rectangular block and its intermediate luminances are interpolated. After all liminances in the 8 8 block are obtained from pixels in the region, they are transformed by 8 8 DCT. The proposed extension/interpolation (EL) method is compared with conventional ones, such as SA-DCT, mean stuffing, etc., under three aspects: peak signal-to-noise ratio (PSNR), hardware complexity, and the flexibility for improvement of performance. Simulation results show that the performance of the proposed method is superior to that of the conventional ones. In addition, we introduce an improved version by repetitively performing the EL method.