This paper discusses the problems of largest similar substructures (in short, LSS) in rooted and unordered trees (in short, R-trees) and those in unrooted and unordered trees (in short, trees). For two R-trees (or trees) T_a and T_b, LSS in T_b to T_a is defined, and two algorithms for finding one of the LSSs for R-trees and that for trees are proposed. The time and space complexities of both algorithms are O_T (m³N_aN_b) and O_S(mN_aN_b), respectively, where m is the largest degree of a vertex of T_a and T_b, and N_a(N_b)is the number of vertices of T_a(T_b).

A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (CO-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai Mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees T_a and T_b are O_T (N²_aN²_a), O_T(m_aN_aN²_b) and O_T(m_am_bN_aN_b), respectively, where N_a(N_b) and m_a(m_b) are the number of vertices in tree T_a(T_b)and the maximum degree of a vertex in T_a(T_b), respectively. The space complexities of these methods are O_S(N_aN_b).

An s-t flow in a directed network is called uncontrollable, when the flow is representable as a positive sum of elementary s-t path flows. In this paper, we discuss the problem Is a given flow uncontrollable?. We show that the problem is NP-complete.

A clique of a graph G(V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time energy-descent optimization algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that RaCLIQUE, the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.

We define the Reallocation Problem to determine whether we can move products from their current store-houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

A directed graph G = (V,E) is called the n-rotator graph if V = {a₁a₂・・・a_n|a₁a₂・・・a_n is a permutation of 1,2,・・・,n} and E = {(a₁a₂・・・a_n,b₁b₂・・・b_n)| for some 2 i n, b₁b₂・・・b_n = a₂・・・a_ia₁a_i+1・・・a_n}. We show that for any pair of distinct nodes in the n-rotator graph, we can construct n - 1 disjoint paths, each length < 2n, connecting the two nodes. We propose a nonadaptive fault-tolerant file transmission algorithm which uses these disjoint paths. Then the probabilistic analysis of its reliability is given.

In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s₁, ・・・, s_k} and T = {t₁,・・・, t_k}, 1kn, of non-faulty nodes in n-dimensional hypercubes H_n, finds k fault-tree node disjoint paths s_it_je, where (j₁, ・・・, J_k) is a permutation of (1, ・・・, k), of length at most n + k in O(kn log k) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in H_n can be found in O(n² log n) time.

A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ², 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.

Polynomials are called permutation polynomials if they induce bijective functions. This paper investigates algebraic properties of permutation polynomials over a finite field, especially properties associated with permutation cycles. A permutation polynomial has a simple structure but good randomness properties suitable for applications. The cycle structure of permutations are considered to be related to randomness. We investigate the algebraic structure from the viewpoint of randomness. First we show the relationship between polynomials and permutations using a matrix equation. Then, we give a general form of a permutation polynomial corresponding to a product C₁C₂・・・C_k of pairwise disjoint cycles. Finally, permutation polynomials with fixed points -or with 2, 3 and 4-cycles -and their compositions are given together with distribution of degree of the permutation polynomials.

This paper presents a combinatiorial characterization of broadcast authentication in which a transmitter broadcasts v messages e₁(s), ・・・, e_v(s) to authenticate a source state s to all n receivers so that any k receivers cannot cheat any other receivers, where e_i is a key. Suppose that each receiver has l keys. First, we prove that k < l if v < n. Then we show an upper bound of n such that n v(v - 1)/l(l - 1) for k = l - 1 and n /+ for k < l - 1. Further, a scheme for k = 1 - 1 which meets the upper bound is presented by using a BIBD and a scheme for k < l - 1 such than n = / is presented by using a Steiner system. Some other efficient schemes are also presented.

In anonymous survey, statistical information by attributes of respondents -such as his gender, age or adress-plays an important role in the interpretation of data. However, giving away all his attributes may cause privacy problem. That is, gathering many attributes may help identifying specifically who responded to the anonymous survey. In this paper, we propose a protocol executed among several `entities in charge' in order to compute statistical information for surveys. The advantage of adopting this protocol is that it does not release extra information of attributes on calculating statistical results. We can show that this protocol is a secure computation in the sense of Micali-Rogaway if played by semi-honest entities. We furthurly give a protocol with zero-knowledge proofs to ensure that the entities are indeed semi-honest.

This paper concerns multiple-valued logical function realized by asynchronous circuit that may have feed-back loops and its completeness problems. The first aim is to give mathematical definition of an asynchronous circuit over multiple-valued logical functions and of the realization of multiple-valued logical function by means of an asynchronous circuit. For asynchronous element, the definition of circuit construction and initialization are very sensitive. A slight modification may have a considerable influence on the completeness. We consider three types of completeness (LF-, GS-, NS-completeness) for a set of multiple-valued logical functions. The LF-completeness means completeness of logical functions realized loop-free cirucit. The GS-completeness means completeness under general initialization assumption. The NS-completeness measn completeness under initialization by input assumption. The second aim is to give a completeness criterion for each type of completeness. This aim is realized for LF-completeness in general case and GS-completeness in ternary case. A completeness criteria for GS-completeness and NS-completeness are given under strong conditions.

We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: ・ for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. ・ A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.

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 := N^d 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.

The Voronoi diagram is the most fundamental and useful concept in computational geometry. To understand impacts of non-Euclidean geometry on computational geometry, this paper investigates the Voronoi diagram in hyperbolic space. We first present characterizations of this diagram by means of the Enclidean Voronoi diagram, and based on them propose efficient algorithms to construct it. Some applications are also mentioned.

A program slice is a set of program statements that directly or indirectly contribute to the values assumed by a set of variables at some program execution point. A few slicing algorithms have proposed to far but none of them are considered from the viewpoint of program modification. In this paper, we define a variable dependence graph (VDG) and show a new slicing algorithm on VDG. We also compare the time complexity of the algorithm with that of other existing algorithms and discuss the suitableness of our algorithm for program modification. As the result of this, we argue our algorithm is suitable for embedding debugging systems.

We propose a parallel parsing algorithm based on Earley's method, which works in O(log²n) time using O(n^4.752) processors on CREW PRAM. This algorithm runs with less number of precessors compared with previously proposed W. Rytter's algorithm.

A calibrating analog-to digital (A/D) converter employing a T-Model neural network is described. The T-Model neural-based A/D converter architecure is presented with particular emphasis on the elimination of local minimum of the Hopfield neural network. Furthermore, a teacher forcing algorithm is presented and used to synthesize the A/D converter and correct errors of the converter due to offset and device mismatch. An experimental A/D converter using standard 5-µm CMOS discrete IC circuits demonstrates high-performance analog-to-digital conversion and calibrating.

The local moment functions for discrete Wigner trispectrum are examined in ambiguity and in time-frequency domain. A concept of multiple and multidimensional circular convolution in frequency domain is introduced into the discrete Wigner higher order time-frequency signal representation of any order. It is shown that this concept based on the 1st order spectra of the signal offers an insight into the properties of inconsistent local moment functions and their representation both in ambiguity and time-frequency domain. It allows to prove that midfrequency crossterms of a multicomponent signal can not be removed by any generalized 4th order ambiguity function which employ kernel function in the ambiguity domain. It is shown, that the concept of multiple convolution in frequency domain can lead to the crossterm-reduced discete time-frequency representations of any order

This paper proposes a new formulation which minimizes the differential entropy for an optimal control problem. The conventional criterion of the optimal regulator control is a standard quadratic cost function E[M{x(t)}²} + N{v(t)}²], where x(t) is a state variable, u(t) is an input value, and M and N are positive weights. However, increasing the number of the variables of the system it is complex to find the solution of the optimal regulator control. Therefore, the simplicity of the solution is required. In contrast to the optimal regulator control, we propose the minimum entropy control which minimizes a differential entropy of the weighted sum of x(t) and u(t). This solution is derived on the assumptions that the linear control and x(t)u(t) 0 are satisfied. As the result, the formula of the minimum entropy control is very simple and clear. This result will be useful for the further work with multi variables of simple control formulation.

We present a new method for the self-tuning control (STC) of nonminimum phase continuous-time systems based on the pole-zero placement. The long division method is used to decompose a polynomial into a stable and unstable polynomials. It is also shown that the effect of unstable zeros on the magnitude of the desired output can be cancelled. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.

Distance properties of trellis codes are of great importance for performance evaluation. In this paper, we use random coding analysis to study the average distance structures of trellis codes. The generating function enumerating the average number of error events of each distances is fully determined in the ensemble of time-varying trellis codes. The results obtained can be used to predict the growth rate of the number of error events at large distance and hence determine the signal-to-noise range in which the transfer function bound for error performance is convergent. Other applications of the average distance structure include a Gilbert-type lower bound on minimum distance.

McEliece and Swanson offerred an upper bound on the decorder error probability of Reed-Solomon codes. In this paper, we investigate the decorder error probability of binary linear block codes and verify its properties, and apply it to binary primitive BCH codes. It is shown that the decorder error probability of an (n,k,t) binary linear block code is determined by P_E uniquely if it is a constant. We derive the decorder error probability of (n,k,t) binary primitive BCH codes with n=2^m-1 and +1 and show that the decorder error probabilities of those codes are close to P_E if codelengh is large and coderate is high. We also compute and analyze the decorder error probabilities of some binary primitive BCH codes.

In this paper cosets of the second order Reed-Muller code of length 2^m, denoted RM_m,2, in the third order Reed-Muller code of the same length, denoted RM_m,3, are studied. The set of cosets, RM_m,3/RM_m,2 is partitioned into blocks. Two cosets are in the same block, if and only if there is a transformation in the general linear group by which one coset is transformed into the other. Two cosets in the same block have the same weight distribution. For the code length less than or equal to 128, the representative coset leader of each block is presented and the weight distribution of cosets in the block is computed. By using these results, the extended code of a cyclic code of length 128 between RM_7,2 and RM_7,3 can be decomposed into a set of cosets in RM_7,3/RM_7,2, and its weight distribution can be derived. Several cyclic codes to length 127 are shown to be equivalent and some new linear unequal error protection codes are found.

It is demonstrated with the Berlekamp-Massey shift-register synthesis algorithm that the linear complexity value of binary complementary sequences is at least 3/4 of the sequence length. For some sequence pairs the linear complexity value can be even 0.98 times the sequence length. In the light of these results strongly non-linear complementary sequences are considered suitable for information security applications employing the spread-spectrum (SS) technique.

It is known that an anticausal IIR filter can be realized in real time by using the time reversed section technique. When combined with a casual IIR filter, the overall transfer function can yield exact linear phase characteristic in theory. This paper presents a new method for designing complex IIR digital filters with exact linear phase. The design problem of IIR filters with exact linear phase can be reduced to magnitude-only filter design. The proposed procedure is based on the formulation of an eigenvalue problem by using Remez exchange algorithm. By solving the eigenvalue problem to compute the real maximum eigenvalue, the solution of the rational interpolation problem can be achieved. Therefore, the optimal filter coefficients are easily obtained through a few iterations. The proposed design algorithm not only retains the speed inherent in Remez exchange algorithm, but also Simplifies the interpolation step because is has been reduced to the computation of the real maximum eigenvalue. Several examples are presented to demonstrate the effectiveness of the proposed method.

The recurrence method is useful for numerical calculation of the Bassel function J_v(x) of complex order v. The necessary total number of the recurrences in this method has been examined for the real order v, but it is known only for limited ranges of the real order v and the variable x, and it is not known for the complex order v. This letter proposes a new algorithm which increases the total number of the recurrences gradually, and which stops the calculation automatically when the approximate Bessel function with a necessary precision is obtained.