This paper is concerned with a concept called universality or completeness of sets of logic devices. Universality characterizes sets of logic devices which can be used for the construction of arbitrary logic circuits. The elemental universality proposed here is the most general condition of universality which covers logic devices with/without delay time and combinational/sequential circuits. The necessary and sufficient condition of elemental universality shows that nonlinearity and nonmonotonicity are essential conditions for the realization of various digital mechanisms.

In this work, we give a true concurrency semantics for FIFO-nets, that are Petri nets in which places behave as queues, tokens take values in a finite alphabet and the firing of a transition depends on sequences on the alphabet. We introduce fn-processes to represent the concurrent behavior of a FIFO-net N during a sequence of transition firings. Fn-processes are modeled by a mapping from a simple FIFO-net without queue sharing and cycles, named FIFO-occurrence net, to N. Moreover, the relation among the firings expressed by the FIFO-occurrence net has been enriched by an ordering relation among the elements of the FIFO-occurrence net representing values entered into a same queue of N. We give a way to build fn-processes step by step in correspondance with a sequence of transition firings and the fn-processes operationally built are all those abstractly defined. The FIFO-occurrence nets of fn-processes have some interesting properties; for example, such nets are always discrete and, consequently, there is at least a transition sequence corresponding to each fn-process.

This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n-1 and is n-1-connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault-free star graph is presented. For a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, which are derived from n-1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search. When faults are encountered, according to that there are n-1 node-disjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a fault-free subgraphs based on the local failure information (the status of all its incident edges). As long as the number f of faults (node faults and/or edge faults) is less than the degree n-1 of the n-star graph, the algorithm can adaptively find a path of length at most d+4f to route messages successfully from a source to a destination, where d is the distance between source and destination.

An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2^(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.

K-randomness and Martin-Lof randomness are among many formalizations of randomness of infinite sequences, and these two are known to be equivalent. We can naturally modify the former to the definition of partial randomness. However, it is not obvious how to modify the latter to the definition of partial randomness. In this paper, we show that we can modify Martin-Lof randomness to a definition of partial randomness that is equivalent to the definition obtained by naturally modifying K-randomness. The basic idea is to modify the notion of measures used in the definition of Martin-Lof tests.

In this paper, we give a solution to the problem of conflict-free access of various slices of data in parallel processor for image processing. Image processing operations require a memory system that permits parallel and conflict-free access of rows, columns, forward diagonals, backward diagonals, and blocks of two-dimensional image array for an arbitrary location. Linear skewing schemes are useful methods for those requirements, but these schemes require complex Euclidean division by prime number. On the contrary, nonlinear skewing schemes such as XOR-schemes have more advantages than the linear ones in address generation, but these schemes allow conflict-free access of some array slices in restricted region. In this paper, we propose a new XOR-scheme which allows conflict-free access of arbitrarily located various slices of data for image processing, with a two-fold the number of memory modules than that of processing elements. Further, we propose an efficient data alignment network which consists of log N + 2-stage multistage interconnection network utilizing Omega network.

Disk arrays are widely accepted as a disk subsystem for video servers due to its high throughput as well as high concurrency. RAID-like disk arrays are usually managed in either RAID level 3 (a request is handled by all the disks in the system) or RAID level 5 (a request is handled by some number of disks subject to the request size) when they are used in video servers, i. e. , either only one video stream is handled at a time in RAID level 3 or a certain number of video streams are handled independently at the same time in RAID level 5. Note that RAID level 3 is inappropriate to handle large number of video streams and RAID level 5 is inefficient to handle multiple video streams since handling continuous video streams is inherently synchronous operation. In this paper, we propose a new video data layout scheme called region-based layout and synchronous management of RAID5 called synchronous RAID5 for disk array used in video servers. It is shown that we can reduce the amount of buffers required to support a given number of video requests by integrating our region-based layout with synchronous RAID5 scheme. Group Sweeping Scheduling (GSS) is used as a basic disk scheduling. We have shown through analysis that our proposed scheme is superior to the existing schemes in the respect of the buffer requirements.

An experiment is reported comparing six pen input strategies for selecting a small target using five diffenent sized targets (1, 3, 5, 7 and 9 dot diameter circles respectively, 0. 36 mm per dot). The results showed that the best strategy, in terms of error rate, selection time and subjective preferences, was the "land-on2" strategy where the target is selected when the pen-tip touches the target for the first time after landing on the screen surface. Moreover, "the smallest maximum size" was determined to be 5 dots (1. 8 mm). This was the largest size among the targets which had a significant main effect on error rate in the six strategies. These results are important for both researchers and designers of pen-based systems.

The new technique for reducing the load latency is presented. This technique, named tunneling-load, utilizes the register specifier buffer in order to reduce the load latency without fetching the data cache speculatively, and thus eliminates the drawback of any load address prediction techniques. As a consequence of the trend toward increasing clock frequency, the internal cache is no longer able to fill the speed gap between the processor and the external memory, and the data cache latency degrades the processor performance. In order to hide this latency, several techniques predicting the load address have been proposed. These techniques carry out the speculative data cache fetching, which causes the explosion of the memory traffic and the pollution of the data cache. The tunneling-load solves these problems. We have evaluated the effects of the tunneling-load, and found that in an in-order-issue superscalar platform the instruction level parallelism is increased by approximately 10%.

In this paper, we extend the Gnaedig's results on termination of order-sorted rewriting. Gnaedig required a condition for order-sorted signatures, called minimality, for the termination proof. We get rid of this restriction by introducing a transformation from a TRS with an arbitrary order-sorted signature to another TRS with a minimal signature, and proving that this transformation preserves termination.

Evaluating analytically computer architecture performance is mostly cheap and quick. However, existing analytical performance evaluation techniques usually have a difficult and time-consuming modeling process. Moreover, existing techniques do not support well the capability for finding the bottleneck and its cause of a target system being evaluated. To address the above problems and to enhance analytical performance evaluation technology, in this paper we propose a software tool that accepts system models described in a specification language, generating an executable program that performs the actual performance evaluation. The whole approach is built on a subsystem-oriented performance evaluation tool, which is, in turn, based on a formal subsystem-oriented performance evaluation technique and a subsystem specification language.

This paper presents a neural network-based control system for Adaptive Noise Control (ANC). The control system derives a secondary signal to destructively interfere with the original noise to cut down the noise power. This paper begins with an introduction to feedback ANC systems and then describes our adaptive algorithm in detail. Three types of noise signals, recorded in destroyer, F16 airplane and MR imaging room respectively, were then applied to our noise control system which was implemented by software. We obtained an average noise power attenuation of about 20 dB. It was shown that our system performed as well as traditional DSP controllers for narrow-band noise and achieved better results for nonlinear broadband noise problems. In this paper we also present a hardware implementation method for the proposed algorithm. This hardware architecture allows fast and efficient field training in new environments and makes real-time real-life applications possible.

In our current work, we attempt to make an automatic diagnostic system of lung cancer based on the analysis of the sputum color images. In order to form general diagnostic rules, we have collected a database with thousands of sputum color images from normal and abnormal subjects. As a first step, in this paper, we present a segmentation method of sputum color images prepared by the Papanicalaou standard staining method. The segmentation is performed based on an energy function minimization using an unsupervised Hopfield neural network (HNN). This HNN have been used for the segmentation of magnetic resonance images (MRI). The results have been acceptable, however the method have some limitations due to the stuck of the network in an early local minimum because the energy landscape in general has more than one local minimum due to the nonconvex nature of the energy surface. To overcome this problem, we have suggested in our previous work some contributions. Similarly to the MRI images, the color images can be considered as multidimensional data as each pixel is represented by its three components in the RGB image planes. To the input of HNN we have applied the RGB components of several sputum images. However, the extreme variations in the gray-levels of the images and the relative contrast among nuclei due to unavoidable staining variations among individual cells, the cytoplasm folds and the debris cells, make the segmentation less accurate and impossible its automatization as the number of regions is difficult to be estimated in advance. On the other hand, the most important objective in processing cell clusters is the detection and accurate segmentation of the nuclei, because most quantitative procedures are based on measurements of nuclear features. For this reason, based on our collected database of sputum color images, we found an algorithm for NonSputum cell masking. Once these masked images are determined, they are given, with some of the RGB components of the raw image, to the input of HNN to make a crisp segmentation by assigning each pixel to label such as Background, Cytoplasm, and Nucleus. The proposed technique has yielded correct segmentation of complex scene of sputum prepared by ordinary manual staining method in most of the tested images selected from our database containing thousands of sputum color images.

Recent progress in neural network research has demonstrated the usefulness of neural networks in a variety of areas. In this work, its application in the spatial resolution improvement of a remotely sensed low resolution thermal infrared image using high spatial resolution of visible and near-infrared images from Landsat TM sensor is described. The same work is done by an algebraic method. The tests developed are explained and examples of the results obtained in each test are shown and compared with each other. The error analysis is also carried out. Future improvements of these methods are evaluated.

Multi-lingual handwriting means the script written with more than one language. In this paper, a hierarchical hidden Markov model network-based approach is proposed for on-line recognition of multi-lingual cursive handwritings. Basic characters of language, language network, and intermixed use of language are modeled with hierarchical relations. Since recognition corresponds to finding an optimal path in such a network, recognition candidates of each language are combined with probability without special treatment. Character labels of handwriting, language modes, and segmentation are obtained simultaneously. However, several difficulties caused by multiple language occurred during recognition. Applied heuristic methods are Markov chain for language mode transitions, pairwise discrimination for confusing pairs, and constrained routines for side effects by language related preprocessing methods. In spite of the addition of other language, recognition accuracy of each language drops negligibly on experimental results of multi-lingual with Hangul, English, and Digit case.

This paper proposes a new approach to recover the sign of local surface curvature of object from three shading images using neural network. The RBF (Radial Basis Function) neural network is used to learn the mapping of three image irradiances to the position on a sphere. Then, the learned neural network maps the image irradiances at the neighbor pixels of the test object taken from three illuminating directions of light sources onto the sphere images taken under the same illuminating condition. Using the property that basic six kinds of surface curvature has the different relative locations of the local five points mapped on the sphere, not only the Gaussian curvature but also the kind of curvature is directly recovered locally from the relation of the locations on the mapped points on the sphere without knowing the values of surface gradient for each point. Further, two step neural networks which combines the forward mapping and its inverse mapping one can be used to get the local confidence estimate for the obtained results. The entire approach is non-parametric, empirical in that no explicit assumptions are made about light source directions or surface reflectance. Results are demonstrated by the experiments for real images.

A novel approach was proposed to recognize the non-rigid 3D objects from their corresponding 2D images by combining the benefits of the principal component analysis and the geometric hashing. For all of the object models to be recognized, we calculated the statistical point features of the training shapes using principal component analysis. The results of the analysis were a vector of eigenvalues and a matrix of eigenvectors. We calculated invariants of the new shapes that undergone a similarity transformation. Then added these invariants and the label of the model to the model database. To recognize objects, we calculated the necessary invariants from an unknown image and used them as the indexing keys to retrieve any possible matches with the model features from the model database. We hypothesized the existence of an instance of the model in the scene if the model's features scored enough hits on the vote count. This approach allowed us to store the rigid and the non-rigid object models in a model database and utilized them to recognize an instance of model from an unknown image.

It becomes essential in practice to improve a processing rate and to divide an image into small segments adjusting a limited memory, because image filing systems handle large images up to A1 size. This paper proposes a new method of an automatic skew normalization, comprising a high-speed skew detection and a distortion-free dividing rotation. We have evaluated the proposed method from the viewpoints of the processing rate and the accuracy for typed documents. As results, the processing rate is 2. 9 times faster than that of a conventional method. A practical processing rate for A1 size documents can be achieved under the condition that the accuracy of a normalized angle is controlled within 0. 3 degrees. Especially, the rotation with dividing can have no error angle, even when the A1 size documents is divided into 200 segments, whereas the conventional method cause the error angle of 1. 68 degrees.

The Asynchronous Transfer Mode (ATM) technique has been accepted as a basis for the future B-ISDN networks. In ATM networks, all information is packetized and transferred in small packets of fixed length, called cells. The packetized information transfer, without flow control between the user and the network and the use of statistical multiplexing, results in a need of a policing mechanism to control the traffic parameters of each virtual connection in order to guarantee the required quality of service (QoS). Policing of the peak cell rate is generally not complex and can be achieved by using a cell spacer or other policing mechanisms (PMs). Monitoring of the mean cell rate is more difficult, but is intended to improve the link utilization when it has to handle bursty traffic sources. Conventional PMs, such as the Leaky Bucket Mechanism (LBM) and Window Mechanisms (WMs), are not well suited to the bursty nature of the sources supported by ATM networks, therefore intelligent PMs are needed. In this paper, we propose a Fuzzy Policing Mechanism (FPM) for multimedia applications over ATM networks. We consider the case of still picture source control. The performance evaluation via simulation shows that the FPM efficiently controls the mean cell rate of the still picture source. The proposed FPM shows a good response behavior against parameter variations and the selectivity characteristics approach very close to the ideal characteristic required for a PM. The FPM has a better characteristic compared with the LBM.

In this paper, dependence of storage capacity of an analogue associative memory model using nonmonotonic neurons on static synaptic noise and static threshold noise is shown. This dependence is analytically calculated by means of the self-consistent signal-to-noise analysis (SCSNA) proposed by Shiino and Fukai. It is known that the storage capacity of an associative memory model can be improved markedly by replacing the usual sigmoid neurons with nonmonotonic ones, and the Hopfield model has theoretically been shown to be fairly robust against introducing the static synaptic noise. In this paper, it is shown that when the monotonicity of neuron is high, the storage capacity decreases rapidly according to an increase of the static synaptic noise. It is also shown that the reduction of the storage capacity is more sensitive to an increase in the static threshold noise than to the increase in the static synaptic noise.

The Heart Rate Variability (HRV) analysis has become vigorous these days. One reason for this is that the HRV analysis investigates the dynamics of the autonomic nervous system activities which control the HRV. The Integral Pulse Frequency Modulation (IPFM) model is a pulse generating mechanism model in the nervous system, that is one of the models which connects the HRV to the autonomic nervous system activities. The IPFM model is a single frequency component model; however, the real HRV has multiple frequency components. Moreover, there are refractory periods after generating action potentials are initiated. Nevertheless, the IPFM model does not consider refractory periods. In order to make sure of the accuracy and the effectiveness of the integral function (IF) method applied to the real data, we consider the absolute refractory periods and two frequency components. In this investigation, the simulated HRV was made with a single and double frequency component using the IPFM model with and without absolute refractory periods. The original generating function of the IPFM model was demodulated by using the instantaneous heart rate tachogram. The power of the instantaneous pulse rate per minute was analyzed by the direct FFT method, the IF FFT method without the absolute refractory periods, and the IF FFT method with the absolute refractory periods. It was concluded that the IF FFT method can demodulate the original generating function accurately.