For two finite disjoint sets P and Q of strings over an alphabet Σ, an alphabet indexing for P, Q by an indexing alphabet Γ with |Γ||Σ| is a mapping :ΣΓ satisfying (P)(Q), where :Σ*Γ* is the homomorphism derived from . We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.

Graph unification is doubtlessly the most expensive process in unification-based grammar parsing since it takes the vast majority of the total parsing time of natural language sentences. A parsing time overload in unification consists in that, in general, no less than 60% of the graph unifications performed actually fail. Thus one way to achieve unification time speed-up is focusing on an efficient, fast way to deal with such unification failures. In this paper, a process, prior to unification itself, capable of filtering or stopping a considerably high percentage of graphs that would fail unification is proposed. This unification-filtering process consists of comparison of signatures that correspond to each one of the graphs to be unified. Unification-filter (hereafter UF) is capable of stopping around 87% of the non-unifiable graphs before unification itself takes place. UF takes significantly less time to detect graphs that do not unify and discard them than it would take to unification to fail the attempt to unify the same graphs. As a result of using UF, unification is performed in an around 71% of the time for the fastest known unification algorithm.

A simple method is presented to calculate the parasitic capacitance effect in the propagation delay of series-connected MOS (SCM) structures. This method divides SCM circuits into two parts and accurately calculates the contribution of each part to the difference from the delay without parasitic capacitances.

The hybrid coding with motion compensated prediction and discrete cosine transform (MC+DCT) has been recognized as the standard technique in motion picture coding. In this paper, a motion estimation processor compatible with ITU-T H.261 and MPEG standards is described. A half-pel precision processing unit is introduced with an exhaustive block matching unit for integer-pel precision search. The necessary processing power for the exhaustive block matching is implemented with a 1-dimensional array structure utilizing a sub-sampling technique. In comparison with the conventional 2-dimensional array structure, path of the data transfer is so simple that the low power dissipation characteristic is obtained. The problem of communication bandwidth to the frame memory, which is a bottleneck of half-pel precision motion estimation, is solved by introducing a candidate pixel buffer into the inter-processor data transfer. A static latch circuit with conflict free operation is newly developed for reducing the power consumption. This chip is capable of processing NTSC-resolution video in real-time at the 40 MHz operation. The chip integrates about 540 k transistors in the 121 mm2 die using 0.8 µm double metal CMOS technology.

This paper discusses pulse responses of multi-conductor transmission lines terminated by linear and nonlinear subnetworks. At first step, the circuit is partitioned into a linear transmission lines and nonlinear subnetworks by the substitution voltage sources. Then, the linear subnetworks are solved by a well-known phasor technique, and the nonlinear subnetworks by a numerical integration technique. The variational value at each iteration is calculated by a frequency domain relaxation method to the associated linearized time-invariant sensitivity circuit. Although the algorithm can be efficiently applied to weakly nonlinear circuits, the convergence ratio for stiff nonlinear circuits becomes very small. Hence, we recommend to introduce a compensation element which plays very important role to weaken the nonlinearity. Thus, our algorithm is very simple and can be efficiently applied to wide classes of nonlinear circuits.

A single-chip architecture for three-dimensional (3-D) computer graphics (CG) is discussed assuming portable equipment with a 3-D CG interface. Based on a discussion of chip requirements, an architecture utilizing DRAM technology is proposed. A 31-Mbit, on-chip DRAM cell array allows a full-color, 480640-pixel frame with two 3-D frame buffers for double buffering and one 2-D frame buffer for superimposed or background images. The on-chip pixel generator produces R, G, B, and Z data in a triangular polygon with a zigzag-scan interpolation algorithm. The on-chip frame synthesizer combines data from one of the 3-D buffers with that from the 2-D buffer to produce superimposed or background 2-D images within a 3-D CG image. Parallel alpha-blending and Z-comparison circuits attached to the DRAM cell array provide a high data I/O rate. Estimation of the chip performance assuming the 0.35-µm CMOS design rule shows the chip size, the drawing speed, on-chip data I/O rate, and power dissipation would be 1413.5-mm, 0.25 million polygons/s, 1 gigabyte/s, and 590 mW at a voltage of 3.3 V, respectively. Based on circuit simulations, the chip can run on a 1.5-V dry cell with a drawing speed of 0.125 million polygons/s and a power dissipation of 61 mW. A scaled-down version of the chip which has an 1-kbit DRAM cell array with an attached alpha-blending circuit is being fabricated for evaluation.

We present a new multi-layer over-the-cell channel router for standard cell layout design using simulated annealing. This new approach, STANZA-M consists of two key features. The first key feature of our router is a new scheme for simulated annealing in which we use a cost function to evaluate both the total net-length and the channel heights, and an effective simulated annealing process by a limited range to obtain an optimal chnnel wiring in practical time. The second feature of our router is a basic layer assignment procedure in which we assign all horizontal wiring inside a channel to feasible layers by considering the height of channel including cell region with a one dimensional channel compaction process. We implemented our three-layer cannel router in C language on a Solbourne Series 5 Work Station (22 MIPS). Experimental results for benchmarks such as Deutsch's Difficult Example and MCNC's PRIMARY1 channel routing problems indicate that STANZA-M can achieve superior results compared to the conventional routers, and the process times are very fast despite the use of simulated annealing.

In real life, our sence of social reality is supported by the institutional basis, group/interpersonal basis, and belief/schema basis. In networked life, in contrast, these natural and ordinary bases are not always warranted because of a lack of institutional backup, the fragility of the group or interpersonal environment, and the noncommonality of our common sense. In order to compensate for these incomplete bases, networkers ar seeking adaptive communication styles. In this process, there emerge three types of communication cultures. One is the name-card exchange" type. This type is realized by communicating our demographic attributes verbally, which is useful for reality construction of the institutional basis. The second is the ideographization" type. In this type, the content of customary nonverbal communication is creatively transformed into various pseudo nonverbal or para-linguistic expressions, which strengthen fragile interpersonal relationships. The last type is the verbalian" type. This type never depends on the interpersonal or institutional basis. The networked reality is constructed solely in the attempt for common sense development among members. By analyzing the content of messages exchanged in four public groups called Forums," the author found that patterns of communication are transformed in a manner adaptive to each Forum's reality. Thier adaptation modes are different and depend on the types of communication culture every Forum pursues. This is contrarty to the psychologists' tendency to assume that there must be common characteristics or rules valid throughout all of the electronic communication situations.

When we design a human interface of a computer-mediated communication (CMC) system, it is important to take a socio-behavioral approach for understanding the nature of the human communication. From this point of view, we conducted experimental observations and post-experimental questionnaires to investigate communicative characteristics in a teleconference using Fujitsu Habitat" visual telecommunication software. We experimentally held the following three kinds of small-group conferences consisting of five geographically distributed participants: (a) teleconference using a visual telecommunication system (Fujitsu Habitat"), (b) teleconference using a real-time keyboard telecommunication system of NIFTY-Serve and (c) live face to face physical conference. Analyses were made on (1) effects of the media on utterance behaviors of conference members, and (2) satisfaction of conference members with communicative functions of the media. Satisfaction was measured by a seven-level rating scale. We found that participants in a telconference held by using Habitat showed significant differences in contents of utterances and the rating of satisfaction with nine communicative functions compared with those of conferences held by using a real-time keyboard telecommunication system and a live face-to-face conference. These results suggest some features that could facilitate multi-participant on-line electronic conferences and conversations.

There are two approaches to implementing the international standard video coding algorithms such as H.261 and MPEG: a programmable DSP approach and a building block approach. The advantages and disadvantages of each are discussed here in detail, and the video coding algorithms and required throughput are also summarized. For more complex standard such as MPEG-, VLSI architecuture became more sophisticated. The DSP approach incorporates special processing engines and the building block approach integrates general-purpose microprocessors. Both approaches are capable of MPEG- NTSC coding in a single chip. Reduction of power consumption is a key issue for video LSIs. Architectures and circuits that reduce the supply voltage while maintaining throughput are summarized. A 0.25-µm, 3-GOPS, 0.5-W, SIMD-VSP for portable MPEG- systems could be made by using architecture-driven voltage scaling as well as feature-size scaling and SOI devices.

Processing elements (PEs) with a dynamically reconfigurable pipeline architecture allow the high-speed calculation of widely used neural model which is multi-layer perceptrons with the backpropagation (BP) learning rule. Its architecture that was proposed for a single chip is extended to multiprocessors' structure. Each PE holds an element of the synaptic weight matrix and the input vector. Multi-local buses, a swapping mechanism of the weight matrix and the input vector, and transfer commands between processor elements allow the implementation of neural networks larger than the physical PE array. Estimated peak performance by the measurement of single processor element is 21.2 MCPS in the evaluation phase and 8.0 MCUPS during the learning phase at a clock frequency of 50 MHz. In the model, multi-layer perceptrons with 768 neurons and 131072 synapses are trained by a BP learning rule. It corresponds to 1357 MCPS and 512 MCUPS with 64 processor elements and 32 neurons in each PE.

This paper describes the circuit design and experimental results of a video-rate 10-b analog-to-digital converter (ADC) suitable for consumer video products, such as high-definition TV sets. Triple-stage conversion scheme combined with two new conversion methods, "Dynamic Sliding Reference Method" and "Triangular Interpolation Method," and an internal Bi-CMOS Sample/Hold circuit have been developed. These conversion methods require no adjustment circuit to fit reference voltages between conversion stages and realize small active area. As a result, a maximum conversion frequency of 16 MHz, acceptable SNRs of 56 dB and 48 dB for 10 kHz and 8 MHz input frequency respectively and small DNLE of 0.75 LSB have been achieved. This ADC is fabricated with 1.2 µm Bi-CMOS technology and integrates very small number of bipolar transistors of 2 K on a small active area of 2.52.7 mm2 and consumes 350 mW.

There has been an increasing demand for telecommunication services that satisfy individual users' requirements such as personal telecommunication services and intelligent network services. This demand for advanced telecommunications services is having a great impact on the control architecture and mechanism. In this paper, we propose a new representation of processing power for telecommunications services, using TPS (Transaction Per Second), instead of BHCA, which has been the most commonly used parameter for conventional telephone networks. In developing an IN benchmark, telecommunications services are compared with the TPC-A (Transaction Processing Performance Council-A) benchmark model based on TPS. This benchmark is then used to estimate the requirements for processing power, which, in turn, indicate the necessity for a distributed control. A layered architecture, compatible architecture, and control mechanism for user services are employed to adapt to the distributed network environment.

A systematic method for locating and computing branches of connecting orbits developed by the authors is outlined. The method is applied to the sine–Gordon and Hodgkin–Huxley equations.

In this paper, the influences of the cross-sectional deformation on the coplanar waveguide (CPW) characteristics for the use of Ti: LiNbO3optical modulator are presented based on quasi-static analysis. In particular, the influences of the changes in the thickness of Ti: LiNbO3 substrate and the cross-sectional shape of electrodes are studied in detail by using the finite element method proposed previously. As a result, it is found that the propagation characteristics of the dominant mode change significantly with the thickness of LiNbO3 substrate when it is less than 100 µm. It is also shown that an inverted trapezoidal deformation of the electrode cross section is promising because a wider electrode gap and thinner electrodes are available in the design of optical modulators.

An optimal control theory has been applied to a biological compartment system to show a method to analyze the control principle of biological system represented by compartments. Present theory has been proposed to afford a theoretical back ground and validity for the strategy of drug administration or control of the anesthetic agent in practical medicine. The instantaneous change of the concentration of a given material within a biological system has been expressed by differential equations. Each compartment has been set to be transferred a material from all other compartments and conversely each compartment sends it to all other compartments. The control input was restricted to be one kind. The performance function involved the deviation from the target value, the rate of change in concentration and the amount of the control variables. The biological system was defined to operate optimally only when the performance function has been minimized during a given time period. By the optimal control theory of Pontoriagin, above biological problem has been converted to a mathematical problem and was solved numerically by multiple shooting method. The calculated trajectory of the optimal control has been asymmetric parabolic one with the maximum at its initiation and the minimum at the middle of total reaction time. This pattern has been consistent with that of probable transient change of the concentration of anesthetic agent when it has been inhalated under the most up to date "Rapid Inhalation Induction" method. The optimal trasient change of the concentration at each compartment has beeb affected by the difference in time dependent nature and the magnitude of the transfer rate. Present theory afforded a method to analyze the control strategy of biological system expressed by compartments model and showed an availability for actual clinical medicine. The optimal control principle must be a most adequate one to describe the Homeostasis in biological system.

We have classified parenchymal echo patterns of cirrhotic liver into 3 types, according to the size of hypoechoic nodular lesions. We have been studying an ultrasonic image diagnosis system using the three–layer back–propagation neural network. In this paper, we will describe the applications of the neural network techniques for recognizing and classifying chronic liver disease, which use the nodular lesions in the Proton density and T2–weighed magnetic resonance images on the gray level of the pixels in the region of interest.

With advances in the speed, bandwidth and reliability of telecommunications networks and in the performance of workstations, distributed processing has become widespread. Information sharing among distributed nodes and its mutual exclusion are of great importance for efficient distributed processing. This paper systematizes and quantitizes a shared memory called Data-Cyclic Shared Memory (DCSM) from the viewpoints of memory organization and access mode. In DCSM, the propagation delay of transmission lines and the data relaying delay in each node are used for information storage, and memory information encapsuled in the form of "memory cells" circulates infinitely in a logical ring type network. The distinctive feature of DCSM, in addition to the way data is stored, is that data and the access control are completely distributed, which contrasts with existing memory where both are centralized. Therefore, there are no performance bottlenecks caused by concentrating memory access. Distributed Shared Memory (DSM), which has a scheme similar to DCSM's, has also been proposed for distributed environments. In DSM, the data is also distributed but the control for accessing each data is centralized. From the viewpoints of memory organization and the access method, DCSM is very flexible. For instance, word length can be spatially varied by defining data size at each address, and each node can be equipped with mechanisms for special functions such as the content address specification and asynchronous report of change in contents. Because of this flexibility, it can be called a "software-defined memory." The analysis also reveals that DCSM has the disadvantages of large access delay and small memory capacity. The capacity can be enlarged by inserting FIFO type queues into the circulation network, and the delay can be shortened by circulating replicas of original memory cells. However, there is a trade off between the maximal capacity and the mean access time. DCSM has many potential applications, such as in the mutual exclusion control of distributed resources.

This paper describes a segmentation method of liver structure from abdominal CT images using a three–layered neural network (NN). Before the NN segmentation, preprocessing is employed to locally enhance the contrast of the region of interest. Postprocessing is also automatically applied after the NN segmentation in order to remove the unwanted spots and smooth the detected boundary. To evaluate the performance of the proposed method, the NN–determined boundaries are compared with those traced by two highly trained surgeons. Our preliminary results show that the proposed method has potential utility in automatic segmentation of liver structure and other organs in the human body.

We prove that the maximum likelihood estimator for estimating 3-D motion from noisy optical flow is not optimal", i.e., there is an unbiased estimator whose covariance matrix is smaller than that of the maximum likelihood estimator when a Gaussian noise distribution is assumed for a sufficiently large number of observed points. Since Gaussian assumption for the noise is given, the maximum likelihood estimator minimizes the mean square error of the observed optical flow. Though the maximum likehood estimator's covariance matrix usually reaches the Cramér-Rao lower bound in many statistical problems when the number of observed points is infinitely large, we show that the maximum likelihood estimator's covariance matrix does not reach the Cramér-Rao lower bound for the estimation of 3-D motion from noisy optical flow under such conditions. We formulate a superior estimator, whose covariance matrix is smaller than that of the maximum likelihood estimator, when the variance of the Gaussian noise is not very small.