Many rewriting systems, including those of terms, strings, graphs, and conjunction of atoms, are used throughout computer science and artificial intelligence. While the concepts of "substitutions," "places" in objects and the "replacement" of "subobjects" by other objects seems to be common to all rewriting systems, there does not exist a common foundation for such systems. At the present time, many of the theories are constructed independently, one for each kind of rewritten object. In the conventional approach, abstract rewriting systems are used to discuss common properties of all rewriting systems. However, they are too abstract to capture properties relating to substructures of objects. This paper aims to provide a first step towards a unified formalization of rewriting systems. The major problem in their formulation may be the formalization of the concept of "places". This has been solved here by employment of the concept of contexts rather than by formalization of places. Places determine subobjects from objects, while, conversely, contexts determine objects from subobjects. A class of rewriting systems, called β rewriting systems, is proposed. It is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement" common to many rewritten objects. The class of β rewriting systems includes very important systems such as semi-Thue systems and Petri Nets. Abstract rewriting systems are also a subclass of β rewriting systems.

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

In this paper, scattering problem of the directional coupler for the slab waveguides are analyzed by the mode-matching method in the sense of least squares for the lowest order even TE mode incidence. It is considered that the analysis of this coupler for the slab waveguides presents the fundamental data to design the directional coupler for the three dimensional waveguides. This directional coupler is composed of three parallel slabs which are placed at equal space in the dielectric medium. Respective slabs are core regions of three respective waveguides. The periodic groove structure of finite extent is formed on the both surfaces of core region of the central waveguide among them. The power of incident TE mode is coupled to other two waveguides through periodic groove structure. The coupled TE mode propagates in the other waveguides to the same or opposite direction for the direction of incident mode which propagates in the waveguide having periodic structure when the Bragg condition is selected appropriately. The scattered field of each region of this directional coupler is described by the superpositions of the plane waves with bandlimited spectra, respectively. These approximate wave functions are determined by the minimization of the mean-square boundary residual. This method results in the simultaneous Fredholm type integral equations of the second kind for these spectra. The first order approximate solutions of the integral equations are derived and the coupling efficiency and scattered fields are analyzed on the basis of those solutions in this paper.

Clothoid or cornu spiral segments were used as transition spirals forming C-and S-shaped curves between circles as well as straight lines in various situations of highway road design. These transitions are the center lines of rail, highway road design. The above C and S-shaped form curves consist one or more transition segments. We study the possibility of using the single transition spirals in the situations that use many transition spirals to form smooth transition spline between circles as well as straight lines. We also compute the bounds for the scaling of such single spirals using the practical equation. This paper is aimed to give a method avoiding non-linear equations by finding range for the scaling factor of the clothoids which can take initially an appropriate closer value from this range.

The approach presented in this paper was intended for extending conventional Markov random field (MRF) models to a more practical problem: the unsupervised and adaptive segmentation of gray-level images. The "unsupervised" segmentation means that all the model parameters, including the number of image classes, are unknown and have to be estimated from the observed image. In addition, the "adaptive" segmentation means that both the region distribution and the image feature within a region are all location-dependent and their corresponding parameters must be estimated from location to location. We estimated local parameters independently from multiple small windows under the assumption that an observed image consists of objects with smooth surfaces, no texture. Due to this assumption, the intensity of each region is a slowly varying function plus noise, and the conventional homogeneous hidden MRF (HMRF) models are appropriate for these windows. In each window, we employed the EM algorithm for maximum-likelihood (ML) parameter estimation, and then, the estimated parameters were used for "maximizer of the posterior marginals" (MPM) segmentation. To keep continuous segments between windows, a scheme for combining window fragments was proposed. The scheme comprises two parts: the programming of windows and the Bayesian merging of window fragments. Finally, a remerging procedure is used as post processing to remove the over-segmented small regions that possibly exist after the Bayesian merging. Since the final segments are obtained from merging, the number of image classes is automatically determined. The use of multiple parallel windows makes our algorithm to be suitable for parallel implementation. The experimental results of real-world images showed that the surfaces (objects) consistent with our reasonable model assumptions were all correctly segmented as connected regions.

We consider the problem of estimating one- and two-dimensional direction of arrivals for arbitrary plane waves in an incoherent/coherent source environment. For the one-dimensional case, we use matrix pencil (MP) method developed by Y. Hua for signal-poles estimation. We then extend this method to estimate the two-dimensional direction of arrivals (2D-DOA), resulting in the "Extended Matrix Pencil" (EMP) method. This method can be applied successfully as much for an incoherent source environment as for a coherent source environment. To study the performance of these methods, in both cases results are compared with the "Total Least Squares-Estimation of Signal Parameters via Rotational Invariance Techniques" (TLS-ESPRIT) and the "Spatial Smoothing-TLS-ESPRIT" (SS-TLS-ESPRIT) methods. The results show that the MP method estimates the DOA more accurately and better than the TLS-ESPRIT and the SS-TLS-ESPRIT, even with few snapshots. Simulation results show that the EMP method, presented in this paper, estimates the 2-DOA better than the other two methods used for comparison.

A novel neural network architecture for image texture classification is introduced. The proposed model (Kernel Modifying Neural Network: KM Net) which incorporates the convolution filter kernel and the classifier in one, enables an automated texture feature extraction in multichannel texture classification through the modification of the kernel and the connection weights by the backpropagation-based training rule. The first layer units working as the convolution kernels are constrained to be an array of Gabor filters, which achieves a most efficient texture feature localization. The following layers work as a classifier of the extracted texture feature vectors. The capability of the KM Net and its training rule is verified using a basic problem on a synthetic texture image. In addition, the possibilities of applying the KM Net to natural texture classification and biological tissue classification using an ultrasonic echo image have been tried.

To reduce the memory access latency on sharedmemory multiprocessors, several prefetching schemes have been proposed. The sequential prefetching scheme is a simple hardware-controlled scheme, which exploits the sequentiality of memory accesses to predict which blocks will be read in the near future. Aggressive sequential prefetching prefetches many blocks on each miss to reduce the miss rates and results in good performance for application programs with high sequentiality. However, conservative sequential prefetching prefetches a few blocks on each miss to avoid prefetching of useless blocks, which shows better performance than aggressive sequential prefetching for application programs with low sequentiality. We analyze the relationship between the sequentiality of application programs and the effectiveness of sequential prefetching on various memory and network latency and propose a new adaptive sequential prefetching scheme. Simply adding a small table to the sequential prefetching scheme, the proposed scheme prefetches a large number of blocks for application programs with high sequentiality and reduces the miss rates significantly, and prefetches a small number of blocks for application programs with low sequentiality and avoids loading useless blocks.

This paper deals with a probabilistic formulation of the diffraction and scattering of a plane wave from a periodic surface randomly deformed by a binary sequence. The scattered wave is shown to have a stochastic Floquet's form, that is a product of a periodic stationary random function and an exponential phase factor. Such a periodic stationary random function is then represented in terms of a harmonic series representation similar to Fourier series, where `Fourier coefficients' are mutually correlated stationary processes rather than constants. The mutually correlated stationary processes are written by binary orthogonal functionals with unknown binary kernels. When the surface deformations are small compared with wavelength, an approximate solution is obtained for low-order binary kernels, from which the scattering cross section, coherently diffracted power and the optical theorem are numerically calculated and are illustrated in figures.

In this paper a new class of single error-correcting fixed block-length (d, k) codes has been proposed. The correctable error types are peak-shift error, insertion or deletion error, symmetric error, etc. The basic technique to construct codes is a systematic construction algorithm of multilevel sequences with a constant Lee weight (TALG algorithm). The coding rate and efficiency are considerably good, and hence the proposed new codes will be very useful for improving the reliability of high density magnetic recording.

Error locating codes were first presented in 1963 by J.K. Wolf and B.Elspas. Since then several code design methods have been proposed. However, their algebraic structure has not yet been clarified. It is apparent that necessary and sufficient conditions for error correcting/detecting codes can be expressed by Hamming distance, but, on the other hand, those for error locating codes cannot always be expressed only by Hamming distance. This paper presents necessary and sufficient conditions for error locating codes by using a newly defined metric and a function. The function represents the number of bytes where Hamming distance between corresponding bytes of two codewords has a certain integer range. These conditions show that an error locating code having special code parameters is an error correcting/detecting code. This concludes that error locating codes include existing bit/byte error correcting/detecting codes in their special cases.

This paper presents a method for land cover classification using the SIR-C/X-SAR imagery based on the maximum likelihood method and the polarimetric filtering. The main feature is to use polarimetric enhanced image information in the pre-processing stage for the classification of SAR imagery. First, polarimetric filtered images are created where a specific target is enhanced versus another, then the image data are incorporated into the feature vector which is essential for the maximum likelihood classification. Specific target classes within the SAR image are categorized according to the maximum likelihood method using the wavelet transform. Addition of polarimetric enhanced image in the preprocessing stage contributes to the increase of classification accuracy. It is shown that the use of polarimetric enhanced images serves efficient classifications of land cover.

The main defficulty in recognizing 3-D objects from 2-D images is matching 2-D information to the 3-D object representation. The multiple-view approach makes this problem easy to solve by reducing the problem to 2-D to 2-D matching problem. This approach models each 3-D object by a collection of 2-D views from various viewing angles and recognizes an object in the image by finding a 2-D view that has the best match to the image. However, if the size of the model database becomes large, the approach requires long time for the recognition of objects. In this paper we present a 3-D object recognition algorithm based on multiple-view approach. To reduce the recognition time, the proposed algorithm uses the coarse-to-fine process previously proposed by the authors and a genetic algorithm-based search scheme for the selection of a best matched model in the database. And, we could verify from the results of the experiments that the algorithm proposed in this paper is useful to speed up the recognition process in multiple-view based object recognition systems.

This paper proposes a family of optimized transmitter and receiver FIR filters for orthogonal frequency division multiplex (OFDM) systems with offset QAM modulation using nonlinear-programming. Two objective functions in the frequency domain (considering both OFDM orthogonal condition and Nyquist condition), least square error (LSE) and minimizing maximal spectral side lobe (Mini-max), are used. The nonlinear programming is implemented with a modified sequential quadratic programming (SQP) algorithm, which guarantees a super-linear convergence. Resultant optimized FIR filters are given with their coefficients and spectra.

This paper analyzes mechanisms of radiated emissions from multilayer printed circuit boards (PCBs) and presents a model to describe the characteristics of such radiation. The radiation mechanism from a four-layer PCB, including the internal power and ground planes, is investigated using a time-domain magnetic field measurement near the PCB. Measurement of the waveform indicates that the main source of radiation is in the power distribution planes. To investigate the characteristics of the radiation from the power distribution, the S21s of the board are measured; the board impedance and the transmission characteristics of the power distribution planes are found to be directly related to the S21 between the two points in the board. The results indicate that the power distribution acts as a transmission line at frequencies higher than 100 MHz. A model that can explain well the radiation properties of these planes treats them as a parallel-plate transmission line interconnected by decoupling circuit comprising a decoupling capacitor and interconnect inductance. From the transmission line theory it is deduced that the line resonance gives rise to strong radiated emissions. The interconnect inductance is an important factor in determining the radiation characteristics.

Let {Xk}k=- be a stationary and ergodic information source, where each Xk takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x-1, x0, x1, ) and D > 0 let the approximate D-match recurrence time be defined by Rn (x, D) = min {m n: dn (Xn1, Xm+nm+1) D}, where Xji denotes the string xixi+1 xj and dn: An An [0, ) is a metric of An induced by d for each n. Let R (D) be the rate distortion function of the source {Xk}k=- relative to the fidelity criterion {dn}. Then it is shown that lim supn-1/n log Rn (X, D) R (D/2) a. s.

This paper proposes a general expansion architecture for constructing large-scale multicast ATM switches with any type of small multicast switch, called the multicast Universal Multistage Interconnection Network (multicast UniMIN). The proposed architecture consists of a buffered distribution network that can perform cell routing and replication simultaneously, and a column of output switch modules (OSMs). The adoption of channel grouping and virtual first-in-first-out (FIFO) buffers results in high delay/throughput performance, and the distributed lookup table scheme for multicast addressing greatly reduces the size of a single lookup table. Analytical and simulation results show that high delay/throughput performance is obtained for both unicast and multicast traffic, and the proposed architecture yields an even better performance for multicast traffic than for unicast traffic. In addition, the multicast UniMIN switch has such good features as modular expandability, simple hardware, and no internal speed-up operation.

A method for recovering the LPC spectrum from a microphone array input signal corrupted by less directional ambient noise is proposed. This method is based on the subspace method, in which directional signal and non-directional noise is classified in the subspace domain using eigenvalue analysis of the spatial correlation matrix. In this paper, the coherent subspace (CSS) method, a broadband extension of the subspace method, is employed. The advantage of this method is that is requires a much smaller number of averages in the time domain for estimating subspace, suitable feature for frame processing such as speech recognition. To enhance the performance of noise reduction, elimination of noise-dominant subspace using projection is further proposed, which is effective when the SNR is low and classification of noise and signals using eigenvalue analysis is difficult.

In recently year, the analysis of power management becomes more important. It is difficult to obtain the maximum power because this is NP-complete. For an n-input circuit, there are 22n different input patterns to be considered. There are two major methods for this problem. First method is to generate input patterns to obtain the maximal power by simulating these generated patterns. This method is called pattern based. The other one uses probability method to estimate the power density of each node of a circuit to calculate the maximal power. In this paper, we use a pattern based method to estimate the maximal power. This method is better than that of probability for the simulation of power activity. In practical applications, these generated patterns can be applied and observe the activity of a circuit. These simulated data can be used to examined the critical paths for performance optimization. A simulated annealing algorithm is proposed to search input patterns for maximum power. Firstly, it transforms this problem into an optimization problem to adapt the simulated annealing method. In this method, there are three strategies for generating the next input patterns, called neighborhood. In the first strategy, it generates the next input pattern by changing the status of all input nodes. In the second strategy, some input nodes are selected and changed randomly.

We consider methods to locate sync words in packet or frame transmission over the additive white Gaussian noise channel. Our starting point is the maximization of the probability of correctly locating the sync word. We extend Massey's original result to the specific synchronization problem, where the sync words is prefixed to the data stream and each packet is preceded by idle transmission or additive white Gaussian noise. We give simulation results for several interesting sync words such as Barker sequences of length 7 and 13 and a sync word of length 17 with good cross-correlation properties. One of the conclusions is that the newly derived formula for the probability of correctly locating the sync word enables the reduction of the false sync detection probability.