We give an overview of the computational complexity of linear and mesh-connected cellular and iterative arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers.

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG, by replacing each hyperedge e={v₁,・・・,v_k} with a new vertex w_e and k edges {w_e, v₁},・・・, {w_e, v_k}, we define an SNDP or ECP in the resulting graph. We show that by approximately solving the SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a d_max⁺-approximation algorithm for the SNDPHG with d_max 3, where d_max (resp. d_max⁺) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d_max⁺(r_max)-approximation algorithm for the SNDPHG, where (i)=_j=1ⁱ(1/j) is the harmonic function and r_max is the maximum connectivity requirement.

The class NQP was proposed as the class of problems that are solvable by non-deterministic quantum Turing machines in polynomial time. In this paper, we introduce non-deterministic quantum finite automata in which the same non-determinism as in non-deterministic quantum Turing machines is applied. We compare non-deterministic quantum finite automata with the classical counterparts, and show that (unlike the case of classical finite automata) the class of languages recognizable by non-deterministic quantum finite automata properly contains the class of all regular languages.

Suppose that there are players in two hierarchical groups and a computationally unlimited eavesdropper. Using a random deal of cards, a player in the higher group wishes to send a one-bit message information-theoretically securely either to all the players in her group or to all the players in the two groups. This can be done by the so-called 2-level key set protocol. In this paper we give a necessary and sufficient condition for the 2-level key set protocol to succeed.

This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k1, there is a language accepted by a realtime one-way deterministic (k+3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.

The mobile computing system is a set of functions on a distributed environment organized to support mobile hosts. In this environment, mobile hosts should be able to move without any constraints and should remain connected to the network even while moving. Also, they should be able to get necessary information regardless of their current location and time. Distributed mutual exclusion methods for supporting distributed algorithms have hitherto been designed for networks only with static hosts. However, with the emergence of mobile computing environments, a new distributed mutual exclusion method needs to be developed for integrating mobile hosts with underlying distributed systems. In the sense, many issues that should be considered stem from three essential properties of mobile computing system such as wireless communication, portability, and mobility. Thus far, distributed mutual exclusion methods for mobile computing environments were designed based on a token ring structure, which has the drawback of requiring high costs in order to locate mobile hosts. In this paper, we propose not only a distributed mutual exclusion method that can reduce such costs by structuring the entire system as a tree-based logical structure but also recovery schemes that can be applied when a node failure occurs. Finally, we evaluate the operation costs for the mutual exclusion scheme and the recovery scheme.

Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.

The stateless-based cache invalidation schemes for wireless environments can be categorized into either asynchronous or synchronous cache invalidation according to the broadcasting way of invalidation report. However, if the asynchronous cache invalidation scheme attempts to support local processing of read-only transaction, a critical problem may occur; the asynchronous invalidation reports provide no guarantee of waiting time for mobile transactions requesting commit. To solve this problem, the server in our approaches broadcasts two kind of messages, asynchronous invalidation report to reduce transaction latency and periodic guide message to avoid the uncertainty of waiting time for the next invalidation report. This paper presents a simulation-based analysis on the performance of the suggesting algorithms. The simulation experiments show that the local processing algorithms of read-only transaction based on asynchronous cache invalidation scheme get better response time than the algorithm based on synchronous cache invalidation scheme.

In 1998, Jan and Tseng proposed two integrated schemes of user authentication and access control which can be used to implement a protection system in distributed computer systems. This paper will analyze the security of both schemes and show that an intruder can easily forge a login, be accepted and logged in as a legal user, and access system resources. We will then propose a modified scheme to withstand our proposed attacks.

This paper presents a high quality 4-kbit/s speech coding algorithm based on a CELP algorithm. The coder operates on speech frames of 20 ms. The algorithm has following four main features: multiple sub-codebooks, backward adaptive mode switching, dispersed-pulse structure, and noise post-processing. The multiple sub-codebooks consist of a pulse-codebook and a random-codebook so that they can handle both signals, noise-like (e.g. unvoiced, stationary noise) and pulse-like (e.g. voiced). The backward adaptive mode switching is performed using decoded parameters; therefore, no additional mode bit is transmitted. The random-codebook size is switched with the backward adaptively selected mode. The subjective quality of unvoiced speech or noise-like signal can be improved by this switching operation because the random-codebook size is greatly increased in such signal mode. The dispersed-pulse structure provides better performance of sparse pulse excitation using dispersed pulses instead of simple unit pulses. The noise post-processing employs a stationary background noise generator for producing stationary noise signal. It significantly improves subjective quality of decoded signal under various background noise conditions. Subjective listening tests are conducted in accordance with ACR and DCR tests. The ACR test results indicate that the fundamental performance of the MDP-CELP is equivalent to that of 32-kbit/s adaptive differential pulse code modulation (ADPCM). The DCR test results show that the performance of the MDP-CELP is equivalent to or better than that of 8-kbit/s conjugate-structure algebraic code excited linear prediction (CS-ACELP) under several background noise conditions.

In this paper, we propose a probabilistic approach to derive an approximate polyhedral description from range data. We first compare several least-squares-based methods for estimation of local normal vectors and select the most robust one based on a reasonable noise model of the range data. Second, we extract the stable planar regions from the range data by examining the distributions of the local normal vectors together with their spatial information in the 2D range image. Instead of segmenting the range data completely, we use only the geometries of the extracted stable planar regions to derive a polyhedral description of the range data. The curved surfaces in the range data are approximated by their extracted plane patches. With a probabilistic approach, the proposed method can be expected to be robust against the noise. Experimental results on real range data from different sources show the effectiveness of the proposed method.

This paper develops a simple algorithm for calculating a polynomial curve or surface in a parallel way. The number of arithmetic operations and the necessary time for the calculation are evaluated in terms of polynomial degree and resolution of a curve and the number of processors used. We made some comparisons between our method and a conventional method for generating polynomial curves and surfaces, especially in computation time and approximation error due to the reduction of the polynomial degree. It is shown that our method can perform fast calculation within tolerable error.

A new approach on designing a finite field multiplier architecture is proposed. The proposed architecture trades reduction in the number of clock cycles with resources. This architecture features high performance, simple structure, scalability and independence on the choice of the finite field, and can be used in high security cryptographic applications such as elliptic curve crypto-systems in large prime Galois Fields (GF(2^m)).

Quantization is an essential step which leads to compression in discrete cosine transform (DCT) domain. In this paper, we show how a statistically non-optimal uniform quantizer can be improved by employing an efficient reconstruction method. For this purpose, we estimate the probability distribution function (PDF) of original DCT coefficients in a decoder. By applying the estimated PDF into the reconstruction process, the dequantization distortion can be reduced. The proposed method can be used practically in any applications where uniform quantizers are used. In particular, it can be used for the quantization scheme of the JPEG and MPEG coding standards.

A novel rough neural network (RNN) structure and its application are proposed in this paper. We principally introduce its architecture and training algorithms: the genetic training algorithm (GA) and the tabu search training algorithm (TSA). We first compare RNN with the conventional NN trained by the BP algorithm in two-dimensional data classification. Then we compare RNN with NN by the same training algorithm (TSA) in functional approximation. Experiment results show that the proposed RNN is more effective than NN, not only in computation time but also in performance.