This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.

This paper addresses the problem of detecting digital line components in a given binary image consisting of n black dots arranged over N N integer grids. The most popular method in computer vision for this purpose is the one called Hough Transform which transforms each black point to a sinusoidal curve to detect digital line components by voting on the dual plane. We start with a definition of a line component to be detected and present several different algorithms based on the definition. The one extreme is the conventional algorithm based on voting on the subdivided dual plane while the other is the one based on topological walk on an arrangement of sinusoidal curves defined by the Hough transform. Some intermediate algorithm based on half-planar range counting is also presented. Finally, we discuss how to incorporate several practical conditions associated with minimum density and restricted maximality.

This is a study on a certain group theoretic property of the set of encryption functions of a block cipher. We have shown how to construct a subset which has this property in a given symmetric group by a computer algebra software GAP4.2 (Groups, Algorithms, and Programming, Version 4.2). These observations on group structures of block ciphers suggest us that we may be able to set a trapdoor based on meet-in-the-middle attack on block ciphers.

We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex s and reaches a goal vertex g after finishing all jobs. In particular, s is called a home location if s = g. The objective of the problem is to find a depth-first routing on T so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations s V can be simultaneously computed in O(n) time, once the problem with a specified home location s V has been solved, where n is the number of vertices. We also show that given a specified start vertex s, the minimum completion times for all goal vertices g can be computed in O(n) time.

Let m 2, n 2, and q 2 be positive integers. Let S_r and S_b be two disjoint sets of points in the plane such that no three points of S_r S_b are collinear, |S_r| = nq, and |S_b| = mq. This paper shows that Kaneko and Kano's conjecture is true, i.e., there are q disjoint convex regions of the plain such that each region includes n points of S_r and m points of S_b. This is a generalization of 2-dimension Ham Sandwich Theorem.

In this paper, we present deterministic parallel algorithms for the convex hull of sorted points and their application to a related problem. The algorithms are proposed for the coarse grained multicomputer (CGM) model. We first propose a cost optimal parallel algorithm for computing the problem with a constant number of communication rounds for n/p p², where n is the size of an input and p is the number of processors. Next we propose a cost optimal algorithm, which is more complicated, for n/p pε, where 0 < ε < 2. From the above two results, we can compute the convex hull of sorted points with O(n/p) computation time and a constant number of communication rounds for n/p pε, where ε > 0. Finally we show an application of our convex hull algorithms. We solve the convex layers for d lines in O((n log n)/p) computation time with a constant number of communication rounds. The algorithm is also cost optimal for the problem.

In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.

This paper proposes an area/time optimizing algorithm in a high-level synthesis system for control-based hardwares. Given a call graph whose node corresponds to a control flow of an application program, the algorithm generates a set of state-transition graphs which represents the input call graph under area and timing constraint. In the algorithm, first state-transition graphs which satisfy only timing constraint are generated and second they are transformed so that they can satisfy area constraint. Since the algorithm is directly applied to control-flow graphs, it can deal with control flows such as bit-wise processes and conditional branches. Further, the algorithm synthesizes more than one hardware architecture candidates from a single call graph for an application program. Designers of an application program can select several good hardware architectures among candidates depending on multiple design criteria. Experimental results for several control-based hardwares demonstrate effectiveness and efficiency of the algorithm.

We consider methods for threshold RSA decryption among distributed agencies without any dealer or trusted party. The first solution is a combination of two techniques by [9] and [7] . It demonstrates the feasibility of combining the distributed key generation and the RSA secure function application. The second solution is another approach making the distributed key distribution simpler and alleviating a burden of each shareholder in comparison with the first scheme. The latter scheme is newly developed technique based on [9] and further inspired by Simmons' protocol-failure of RSA (we believe that it is very interesting that a "protocol failure attack" be turned into a constructive method). Our comparison between these two schemes indicates a new measure of the performance of a distributed cryptographic protocol that consists of multiple stages.

In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the right-most word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then, under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.

This paper describes simple and efficient (linear-preserving) reductions between the Decision Diffie-Hellman problem and related problems.

Multi-level divide-and-conquer (MDC) is a generalized divide-and-conquer technique, which consists of more than one division step organized hierarchically. In this paper, we investigate the paradigm of the MDC and show that it is an efficient technique for designing parallel algorithms. The following parallel algorithms are used for studying the MDC: finding the convex hull of discs, finding the upper envelope of line segments, finding the farthest neighbors of a convex polygon and finding all the row maxima of a totally monotone matrix. The third and the fourth algorithms are newly presented. Our discussion is based on the EREW PRAM, but the methods discussed here can be applied to any parallel computation models.

Adaptation of software components to the requirements is one of the key concerns in Component Based Software Development (CBSD). In this paper, we propose a formal approach to compose component based systems which are adaptable to the requirements. We focus on the functional aspects of software components and requirements, which are expressed in S-sorted functions. Those S-sorted functions are transformed into Colored Petri Nets (CPN) models in order to evaluate connectivity between the components, and to evaluate adaptability of composed systems to the requirements. The connectivity is measured based on colors or data types in CPN, while the adaptability is measured based on functional equivalency. We introduce simple glue codes to connect the components each other. The paper focuses on business applications, however the proposed approach can be applied to any other domains as far as the functional adaptability is concerned.

It is known that the problem of determining, given a planar graph G and an integer m, whether there exists a congestion-1 embedding of G into an m k-grid is NP-complete for a fixed integer k 3. It is also known that the problem for k = 3 is NP-complete even if G is restricted to an acyclic graph. The complexity of the problem for k = 2 was left open. In this paper, we show that for k = 2, the problem can be solved in polynomial time if G is restricted to a tree, while the problem is NP-complete even if G is restricted to an acyclic graph.

Elliptic curves E_m: By² = x³+Ax²+x are suitable for cryptographic use because fast addition operations can be defined over E_m. In elliptic curve cryptosystems, encryption/decryption involves multiplying a point P on E_m by a large integer n. In this paper, we propose a fast algorithm for computing such scalar multiplication over E_m. The new algorithm requires fewer operations than previously proposed algorithms. As a result, elliptic curve cryptosystems based on E_m can be speeded up by using the new algorithm.

Elliptic curve cryptosystems are based on the elliptic curve discrete logarithm problem (ECDLP). If elliptic curve cryptosystems avoid FR-reduction and anomalous elliptic curve over F_q, then with current knowledge we can construct elliptic curve cryptosystems over a smaller definition field. ECDLP has an interesting property that the security deeply depends on elliptic curve traces rather than definition fields, which does not occur in the case of the discrete logarithm problem (DLP). Therefore it is important to characterize elliptic curve traces explicitly from the security point of view. As for FR-reduction, supersingular elliptic curves or elliptic curve E/F_q with trace 2 have been reported to be vulnerable. However unfortunately these have been only results that characterize elliptic curve traces explicitly for FR- and MOV-reductions. More importantly, the secure trace against FR-reduction has not been reported at all. Elliptic curves with the secure trace means that the reduced extension degree is always higher than a certain level. In this paper, we aim at characterizing elliptic curve traces by FR-reduction and investigate explicit conditions of traces vulnerable or secure against FR-reduction. We show new explicit conditions of elliptic curve traces for FR-reduction. We also present algorithms to construct such elliptic curves, which have relation to famous number theory problems.

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)^ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k n^ε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n^1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k n^ε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O^{((n α(n) log3 n)/p)} time using p processors, where 1 p n^1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

The uniform switching system is the family of non-linear n m binary arrays constrained such that all columns are from the constant weight k vectors and all rows have weights divisible by p > 0. For this system, we present a cardinality formula and an enumerative algorithm.

In order to compute gcd of polynomials, the Euclidean algorithm is used. We estimate the complexities of known Euclidean algorithms. Further, we propose a heuristic Euclidean algorithm. This is faster than ordinary methods under some special conditions by the use of the recurrent Karatsuba multiplication.

In recent years, the study of the security of Elliptic Curve Cryptosystems (ECCs) have been received much attention. The MOV algorithm, which reduces the elliptic curve discrete log problem (ECDLP) to the discrete log problem in finite fields with the Weil pairing, is a representative attack on ECCs. Recently Kanayama et al. observed a realization of the MOV algorithm for non-supersingular elliptic curves under the weakest condition. Shikata et al. independently considered a realization of the MOV algorithm for non-supersingular elliptic curves and proposed a generalization of the MOV algorithm. This short note explicitly shows that, under a usual cryptographical condition, we can apply the MOV algorithm to non-supersingular elliptic curves by using the multiplication by constant maps as in the case of supersingular. Namely, it is explicitly showed that we don't need such a generalization in order to realize the MOV algorithm for non-supersingular elliptic curves under a usual cryptographical condition.

The trivalent Cayley graph TC_n was introduced and investigated in [1],[2]. Though "the diameter" was presented in [2], unfortunately it was not the diameter but an upper bound of it. In this paper, a lower bound of the diameter dia(TC_n) of the trivalent Cayley graph TC_n is investigated and the formula dia(TC_n) = 2n - 2 for n 3 is established.

We present a new family of algorithms that solve the bias problem in the equation-error based adaptive infinite impulse response (IIR) filtering. A novel constraint, called the constant-norm constraint, unifies the quadratic constraint and the monic one. By imposing the monic constraint on the mean square error (MSE) optimization, the merits of both constraints are inherited and the shortcomings are overcome. A new cost function based on the constant-norm constraint and Lagrange multiplier is defined. Minimizing the cost function gives birth to a new family of bias-free adaptive IIR filtering algorithms. For example, two efficient algorithms belonging to the family are proposed. The analysis of the stationary points is presented to show that the proposed methods can indeed produce bias-free parameter estimates in the presence of white noise. The simulation results demonstrate that the proposed methods indeed produce unbiased parameter estimation, while being simple both in computation and implementation.

This paper presents the design of a modulated complex lapped transform (MCLT) processor and its complex programmable logic device (CPLD) implementation. The MCLT is a 2x oversampled DFT filter bank; it performs well in applications that require a complex filter bank, such as noise reduction and acoustic echo cancellation. First, we show that the MCLT can be mapped to a Fast Fourier Transform (FFT). Then efficient implementation for fast MCLT computation is realized on the CPLD hardware using pipelining techniques. Detailed circuit design for the MLCT processor is presented, as well as timing diagrams for design verification and performance evaluation.

We have built an active omni-directional range range sensor that can obtain an omni-directional depth data through the use of a laser conic plane and a conic mirror. In the navigation of the mobile robot, the proposed sensor system makes a laser conic plane by rotating the laser point source at high speed which creates a two-dimensional depth map, in real time, once an image is captured. Also, since the proposed sensor system measures the actual distance of the target objects, it is able to apply the proposed sensor system to other measurement tasks.

This paper studies an integrate-and-fire circuit with a periodic input. It has two states and has rich dynamics: as a DC input varies, it can exhibit period doubling bifurcation to chaos; as a periodic input is applied, the periodic or chaotic phenomenon (for a DC input) is changed into interesting synchronous or asynchronous phenomenon. Using a mapping procedure, we can elucidate parameter subspace in which the synchronous phenomena occur. Using a test circuit, typical phenomena can be verified in the laboratory.

We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the sub-network extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.

A digit-recurrence algorithm for cube rooting is proposed. In cube rooting, the digit-recurrence equation of the residual includes the square of the partial result of the cube root. In the proposed algorithm, the square of the partial result is kept, and the square, as well as the residual, is updated by addition/subtraction, shift, and multiplication by one or two digits. Different specific versions of the algorithm are possible, depending on the radix, the digit set of the cube root, and etc. Any version of the algorithm can be implemented as a sequential (folded) circuit or a combinational (unfolded) circuit, which is suitable for VLSI realization.

This paper conducts performance evaluation and performs simulation for a code division multiple access (CDMA) system when channel bands of multiple neighboring CDMA/DSSS are overlapped in time domain. It is assumed that all systems adopt direct-sequence spread-spectrum (DSSS) technique and are BPSK modulated by the different carrier frequencies. Automatic power control (APC) is also applied in the interfered system such that the receiver gets the same power from all users. Without loss generality, an additive white Gaussian noise (AWGN) channel is also assumed during analysis. In this paper, the analytic solution of the signal to noise ratio (SNR) is first derived in which both CDMA systems are modulated by different carrier frequencies. We have the results by simulation with Δ f = 0 and Δ f = 1 MHz, respectively. This analysis is good for general cases; and the results show an excellent computational performance. In particular, the result is very close to Pursley's result, when the systems have the same code length with no carrier difference.

In this report, we propose an integrated lossy and lossless image coding, which is possible to be implemented on one architecture, based on combination of lossless wavelet transform (LWT) and lossy-lossless multi-channel prediction (LLMP). The LWT is applied to divide input signals into frequency subbands as octave-band decomposition, whereas the LLMP is designed as a non-separable two-dimensional filter bank including quantization step size and local decoding to enhance coding performance in both lossless coding and lossy coding. Its filter coefficients are determined to minimize total bit rate for lossless coding, and the optimum quantization step size is applied to maximize lossy coding gain. The local decoding is applied to avoid quantization error effect. The experimental results confirm effectiveness of our proposed method.

We have designed a 32-bit RISC microprocessor with 16-/32-bit fixed-point DSP functionality. This processor, called YD-RISC, combines both general-purpose microprocessor and digital signal processor (DSP) functionality using the reduced instruction set computer (RISC) design principles. It has functional units for arithmetic operation, digital signal processing (DSP) and memory access. They operate in parallel in order to remove stall cycles after DSP or load/store instructions, which usually need one or more issue latency cycles in addition to the first issue cycle. High performance was achieved with these parallel functional units while adopting a sophisticated five-stage pipeline structure. The pipelined DSP unit can execute one 32-bit multiply-accumulate (MAC) or 16-bit complex multiply instruction every one or two cycles through two 17-b 17-b multipliers and an operand examination logic circuit. Power-saving techniques such as power-down mode and disabling execution blocks allow low power consumption. In the design of this processor, we use logic synthesis and automatic place-and-route. This top-down approach shortens design time, while a high clock frequency is achieved by refining the processor architecture.

Based on the use of Berlekamp-Massey algorithm, six conjectures for the linear complexity (LC) of some Kronecker sequences of two and three component codes are given. Components were chosen from the families of Gold, Kasami, Barker, Golay complementary and M-sequences. Typically, the LC value is a large part of the code length. The LC value of the outermost code influences mostly on the LC value.

In this paper, we present improved alternative sequential filter-edge detector using generalized directional morphological filters. Based on the properties of effective noise removal and detail preservation of the generalized directional morphological filters, we apply these filters to edge detection of noisy images. The performance of the edge detection in the presence of mixed noise is evaluated. Simulations show that edge detection method using generalized directional morphological filters can also improve the performance.