Parallel multiple context-free grammar (PMCFG) and multiple context-free grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple context-free language (MCFL) and parallel multiple context-free language (PMCFL) can be solved in O(ne) time and O(ne+1) time, respectively, where e is a constant which depends only on a given MCFG or PMCFG. In this paper, we propose the following two algorithms. (1) An algorithm which reduces the recognition problem for MCFL to the boolean matrices multiplication problem. (2) An algorithm which reduces the recognition problem for PMCFL to the recognition problem for MCFL. The time complexity of these algorithms is O(ne-3i+1 M(ni)) where e and i are constants which depend only on a given MCFG or PMCFG, and M(k) is the time needed for multiplying two k k boolean matrices. The proposed algorithms are faster than the known fastest algorithms unless e=e, i=1 for MCFG, and e=e, i=0 for PMCFG.

A unified theory for the characteristics of dual modes in a circular resonator is elucidated in simple analytical expressions. First, a circular resonator is considered as a ring transmission line which allows two oppositely traveling waves. The essential quantities that characterize a transmission line, i. e. , the propagation constant and characteristic impedance are obtained theoretically and/or experimentally. Secondly, any circular resonator is described by a ring resonator model which can be treated analytically, and the resonant frequencies are obtained when perturbations are added along the periphery of a circular resonator. A two stage BPF is created by adding I/O ports to the perturbed circular resonator. Its center frequency and bandwidth is calculated based on the ring resonator model. The circuit condition for obtaining two attenuation poles at both sides of the passband is given together with the method for their control.

Differences in the behavior of dispenser cathodes and oxide cathodes in laminar-flow type and crossover type electron guns were investigated by experiments and simulations under high-current-density conditions. When an oxide cathode is operated under such conditions, the heating effect due to Joule heat in the oxide layer exceeds the cooling effect, depending on the product of the work function and the cathode current, resulting in a rise in the cathode temperature. This rise in cathode temperature aggravates deterioration of emission characteristics during the life of an oxide cathode. In the case of the dispenser cathode, however, the cathode temperature decreases under high-current-density conditions. When an oxide cathode in a crossover type electron gun is operated, equipotential surfaces are formed in the curved surface in the oxide layer. The formation of an equipotential surface leads to relaxation of the loading. It is considered that this is the reason for the longer life of an oxide cathode in a crossover type electron gun than that of an oxide cathode in a laminar-flow type electron gun.

Cursor RAMs have been composed of two memory planes. A cursor pattern is stored in these planes with 2-bit data depth. While the pixel port requires data from both planes at the same time, the MPU port accesses either one of the planes at a time. Since the address space is defined differently between the ports, conventional cursor RAMs could not have dealt with these different access ways at real time. This paper proposes a dual port cursor RAM with a dynamic data alignment architecture. The architecture processes the different access ways at real time, and reduces a large amount of control circuitry. Conventional cursor RAMs have been organized with a single port memory because dual port memory cells have been large. We have applied the port swap architecture which has reduced the cell size. The control block is further simplified because the controller no longer emulate a dual port memory. The cursor RAM with these architectures is fabricated with a double metal 0. 5 µm CMOS process technology. The active area is 1. 51. 6 mm2 including a couple of shift registers and a control block. It operates up to 263 MHz at the supply voltage of 3. 3 V.

This letter reports on the condition for applying a feedback connection to a deterministic finite automata. First we define the partial delayed dependence condition for the feedback connection, and then consider problems related to the completeness problem of automata.

Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of programs may degrade considerably. In this paper, we focus on automatic generation of communication routines for multi-dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some experimental results show the efficiency and flexibility of our techniques compared to the other redistribution works.

We apply evolutionary algorithms to neural network model of associative memory. In the model, some of the appropriate configurations of the synaptic weights allow the network to store a number of patterns as an associative memory. For example, the so-called Hebbian rule prescribes one such configuration. However, if the number of patterns to be stored exceeds a critical amount (over-loaded), the ability to store patterns collapses more or less. Or, synaptic weights chosen at random do not have such an ability. In this paper, we describe a genetic algorithm which successfully evolves both the random synapses and over-loaded Hebbian synapses to function as associative memory by adaptively pruning some of the synaptic connections. Although many authors have shown that the model is robust against pruning a fraction of synaptic connections, improvement of performance by pruning has not been explored, as far as we know.

A homeotropic liquid crystal display utilizing a liquid crystal with positive dielectric anisotropy, 13. 3" XGA TFT-LCD, has been fabricated. The rubbing-free device, appears black in the absence of electric field. When an electric field generated by interdigital electrodes is applied, a bend deformation of molecular director to the direction of the field occurs and thus the cell transmits light, showing brightness uniformity in all directions owing to the dual domainlike director configuration. With an addition of negative-birefringent film, this device shows excellent viewing angle characteristics.

Space Division Multiple Access (SDMA) will form an important part of the new Wideband Code Division Multiple Access (WCDMA) standard that will realize the Universal Mobile Telephone System (UMTS). This paper addresses a few issues of importance when SDMA techniques are used in a cellular CDMA system. Firstly, a brief overview of SDMA techniques are presented followed by a theoretical analysis of a SDMA/CDMA system. The analysis is focused on a single cell, multipath Rayleigh fading scenario with imperfect power control. As system performance measure Bit Error Rate (BER) is used to investigate the influence of user location, number of antennas and power control error. An important parameter in a SDMA system is the antenna array element spacing. In our analysis a Uniform Linear Array (ULA) is considered and a measure is defined to determine the optimal antenna element spacing in a CDMA cellular environment. Normally the mobile users in a cell are assumed to be uniformly distributed in cellular performance calculations. To reflect a more realistic situation, we propose a novel probability density function for the non-uniform distribution of the mobile users in the cell. It is shown that multipath and imperfect power control, even with antenna arrays, reduces the system performance substantially.

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

One of unique features of CDMA slotted ALOHA (CDMA S-ALOHA) is that user must synchronize his transmission to given slot. Thus orthogonal sequence as spreading sequence would achieve ideal throughput if each of packets accomplish perfect synchronization. In the presence of any ambiguity in synchronizations, however, quasi-synchronous (QS) sequences suit well with CDMA S-ALOHA system. In this paper, we introduce new QS-sequences obtained from the orthogonal Gold sequences and discuss their performance when applying to CDMA S-ALOHA systems. As a result, withstanding to access timing error, good performance is ensured with this sequence under the environment of AWGN, MAI (multiple access interference) and frequency non-selective fading, that is, micro or pico cellular systems and indoor wireless LANs.

In this paper, we describe the implementation of the proposed single user type CDMA adaptive interference canceller (AIC) with RAKE structure in the developed testbed for the base station, and evaluate its performance in the multiuser and multipath fading environment. Laboratory experiment demonstrates that the AIC receiver is much more near-far resistant than the conventional matched filter (MF) receiver in the multiuser case. When the power of the other users is 6 dB larger than that of the desired user, the AIC receiver can achieve the BER of 10-3 at C/PG = 33. 3 % in the 2-path fading channel, while the MF receiver cannot achieve the BER at C/PG of more than 20. 8%. Furthermore, we evaluate the effect of transmission power reduction in the transmitter with transmission power control (TPC). The experimental result shows that the required transmission power can be greatly reduced by 3. 0 dB and 9. 2 dB with the AIC receiver at C/PG = 29. 2 % and 33. 3%, respectively.

Low bit-rate speech and audio codings are key technologies for multimedia communications. A number of coding scheme have been developed for various applications. In Internet application, good speech and audio quality at very low bit-rate (8-16 kb/s) is valuable. Two recently proposed speech and audio-coding schemes, CS-ACELP (Conjugate Structure Algebraic Code Excited Linear Prediction, standardized by the ITU-T in Recommendation G. 729) and TwinVQ (Transform-domain Weighted INterleave Vector Quantization, one of the candidates for MPEG-4 audio) were compared from the viewpoints of coding schemes and quality. Although there are significant differences in their basic structures and frame lengths, this paper describes that both use the same compression techniques, such as LPC (Linear Predictive Coding)-analysis pitch-period estimation and vector quantization. While CS-ACELP provides toll quality for speech at 8 kb/s, the quality it provides for music signals is insufficient. The TwinVQ transform coder is based on LPC and vector quantization and is also capable of operating at 8 kb/s. Evaluation of these two schemes in terms of their fundamental technologies, quality, delay, and complexity showed that the quality of TwinVQ for music signals is better than that of CS-ACELP, and that the quality of CS-ACELP is better for speech signals. Therefore, TwinVQ may be better suited for one-directional Internet applications, and CS-ACELP may be better for two-directional communication.

This paper describes a factorization-based algorithm that reconstructs 3D object structure as well as motion from a set of multiple uncalibrated perspective images. The factorization method introduced by Tomasi-Kanade is believed to be applicable under the assumption of linear approximations of imaging system. In this paper we describe that the method can be extended to the case of truly perspective images if projective depths are recovered. We established this fact by interpreting their purely mathematical theory in terms of the projective geometry of the imaging system and thereby, giving physical meanings to the parameters involved. We also provide a method to recover them using the fundamental matrices and epipoles estimated from pairs of images in the image set. Our method is applicable for general cases where the images are not taken by a single moving camera but by different cameras having individual camera parameters. The experimental results clearly demonstrates the feasibility of the proposed method.

Telecommunication technologies are making relentless progress. In this circumstance, network cost must be evaluated to assess the effectiveness of emerging technologies. To do such an evaluation efficiently, it is necessary to develop a software tool that can calculate the network cost independent of the employed technologies. This paper describes computational techniques used in developing such a software tool. First, the functional requirements are identified to establish a flexible tool that is applicable to a wide range of technologies. One of the required functions is the function that computes the resource amount and the network cost from the given conditions such as traffic demands, a cable duct network, multiplex hierarchy and the specifications of network elements employed. As this computing function, the paper proposes an appropriate path classification scheme that enables us to evaluate the resource amount correctly when a service protection technique is applied to the target network. Namely, the proposed scheme yields evaluations that isolate the primary path route from the backup path route. This isolation is not always provided without classification. In addition, a classification of network elements is also derived for valid estimation of the necessary interface board number, which is a basis of estimating the required network element amount. This classification allows us to identify the exact points of path cross-connection and termination, which affects the number of interface boards. This paper presents the computing procedures that realize path grouping and an estimation of network elements using these classification schemes. Finally, the paper describes a prototype of the tool to confirm the feasibility and effectiveness of the proposed schemes.

In ATM Network, the VBR (Variable Bit Rate) service category is used to accommodate TCP/IP traffic. In an international ATM network with large propagation delay, higher TCP throughput can be obtained by use of window scale option. In order to accommodate TCP traffic with window scale option effectively, it is required to select appropriate values of VBR parameters, i. e. SCR (Sustainable Cell Rate) and MBS (Maximum Burst Size), and to evaluate the impact of UPC (Usage Parameter Control) function on TCP throughput. We have studied those technical issues for the conventional TCP, but the results cannot be applied to TCP traffic with the window scale option due to the TCP terminal performance and the large window size. In this paper, we proposed VBR parameter determination method for TCP with the window scale option and evaluated the values in each condition. These results show that the determined MBS is much smaller than the burst length of TCP segments especially using low performance TCP terminals. Furthermore, we also discuss some experimental results of TCP throughput degradation due to UPC function. It shows that the throughput of TCP with large window size is degraded when the SCR and MBS values used in ATM switch are smaller than the determined values.

This paper presents a performance comparison between the single-stream and the multi-stream approaches to lip synchronization of live media (voice and video). The former transmits a single transport stream of interleaved voice and video, while the latter treats the two media as separate transport streams. Each approach has an option not to exert the synchronization control at the destination, which leads to four basic schemes. On an interconnected ATM-wireless LAN, we implemented the four basic schemes with RTP/RTCP on top of UDP and two variants which exercise dynamic resolution control of JPEG video. Making the performance measurement of the six schemes, we compare them to identify and evaluate advantages and disadvantages of each approach. We then show that the performance difference between the two approaches is small and that the dynamic resolution control improves the synchronization quality.

When multiple flows including continuous media streams are simultaneously sent from a computer, allocation and management of both processor capacity and network bandwidth need to be considered. We propose a framework of Quality of Service (QoS) management inside a sending host that controls execution of sending threads in consideration of utilization of processor capacity and network bandwidth. To distinguish from flows which require only best-effort service, we call a flow which requires a specific rate of service "reserved flow. " To guarantee QoS of such reserved flow both in processor- and network-intensive cases in a sending host, processor capacity reserve is allocated such that the rate of each reserved flow is attained and non-conforming data are policed before they are transmitted. Processor Capacity Manager and the network device driver exchange information in a cooperative manner to support the rate adaptive allocation of processor capacity reserve. In this paper, we describe design and implementation of our framework on RT-Mach. The results of performance evaluations demonstrate that our scheme performs well for full-duplex Ethernet.

QoS of a multimedia interactive satellite communications system, which uses a satellite circuit for downlinks and a terrestrial network for uplinks, has been measured and evaluated under inferior satellite circuit conditions. Our attention in this paper is focused on TCP throughput as the most significant QoS, and experiments and analysis on TCP throughput were performed. The measured results are in good agreement with theoretical values calculated by taking congestion avoidance algorithms of TCP into consideration. As a result, we were able to verify that the TCP throughput declines radically when the low signal quality of a satellite circuit causes packet retransmission to occur. In this case, congestion avoidance works to reduce network congestion. The congestion avoidance increases the value of a retransmission timer and decreases the window size even if the network is not congested. Assuming that throughput deterioration is caused by rain fade, the total time when the throughput declines is less than 4 hours a year in Tokyo, and the results show the system can be put to practical use.

In this paper, a new overload control strategy is proposed for a call control processor (CCP) in the base station controller (BSC) and processor utilization is measured. The proposed overload control strategy can regulate the call attempts by adopting measured processor utilization. A function, specifically a linear interpolation function based on Inverse Transform theory is used to convert controlled predictive average load rate in a call rejection rate. Then a call admission rate is obtained from the call rejection rate. Simulation shows that the proposed algorithm yields better performance than the conventional algorithm does under the heavy transient overload status in terms of call admission rate.