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.

This paper addresses the important issue of estimating realistic grasping postures, and presents a methodology and algorithm to automate the generation of hand and body postures during the grasp of arbitrary shaped objects. Predefined body postures stored in a database are generalized to adapt to a specific grasp using inverse kinematics. The reachable space is represented discretely dividing into small subvolumes, which enables to construct the database. The paper also addresses some common problems of articulated figure animation. A new approach for body positioning with kinematic constraints on both hands is described. An efficient and accurate manipulation of joint constraints is presented. Obtained results are quite satisfactory, and some of them are shown in the paper. The proposed algorithms can find application in the motion of virtual actors, all kinds of animation systems including human motion, robotics and some other fields such as medicine, for instance, to move the artificial limbs of handicapped people in a natural way.

This paper presents a type inference algorithm for a logic language, HS. The algorithm uses a program transformation, SPS, to given programs as a type inference. This method is theoretically clear, because applying it to given programs is equal to executing it partially. No other additional framework is needed for our approach. In contrast, many studies on type inference for logic languages are based on Mycroft and O'Keefe's famous algorithm, which was initially developed for functional languages. Therefore, the meanings of the algorithms are theoretically unclear in the domain of logic languages. Our type inference is flexible. Users of the type inference system can specify the types of objects abstractly (weakly) if the types are not exactly known, or they can specify them particularly (strongly) if the types are exactly known. Both kinds of programs are inferred for types. In contrast, many type inference systems accept purely untyped programs. Thus, with these two features, our method is simple and flexible.

An associative memory model with a forgetting process a la Mezard et al. is investigated for a piecewise nonmonotonic output function by the SCSNA proposed by Shiino and Fukai. Similar to the formal monotonic two-state model analyzed by Mezard et al. , the discussed nonmonotonic model is also free from a catastrophic deterioration of memory due to overloading. We theoretically obtain a relationship between the storage capacity and the forgetting rate, and find that there is an optimal value of forgetting rate, at which the storage capacity is maximized for the given nonmonotonicity. The maximal storage capacity and capacity ratio (a ratio of the storage capacity for the conventional correlation learning rule to the maximal storage capacity) increase with nonmonotonicity, whereas the optimal forgetting rate decreases with nonmonotonicity.

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.

Network survivability against various unexpected failures is one of indispensable technologies for the B-ISDN infrastructure. Self-healing algorithm is the technique to automatically restore the failed VP's (virtual paths) in the backbone ATM network. Since the B-ISDN transports various kinds of traffic with various levels of priority (Grade of Service: GoS), the effective self-healing algorithm should orderly restore the failed VP's based on the priority of their traversing traffic. This paper proposes the priority based restoring self-healing algorithm, which realizes the priority based restoring function by the two-timer mechanisms and a simple capacity reserving protocol. The simulation results show that the proposed algorithm can schedule the restoration process so that the failed VP's with higher priority are restored before the others with lower priority. In addition, the significant improvement in restoration speed for the highest priority traffic class has been achieved.

In order to enhance the energy transfer efficiency in a Cherenkov laser, we propose to use a tapered waveguide with a dielectric thickness properly varied stepwise in the longitudinal direction. With the aid of particle simulation, we investigate the nonlinear characteristics of the Cherenkov laser with the tapered waveguide, demonstrating the effectiveness of our proposal for efficiency enhancement.

In a shared-memory multiprocessor, shared data are usually accessed in a critical section that is protected by a lock variable. Therefore, the order of accesses by multiple processors to the shared data corresponds to the order of acquiring the ownership of the lock variable. This paper presents a selective write-update protocol, where data modified in a critical section are stored in a write cache and, at a synchronization point, they are transferred only to the processor that will execute the critical section following the current processor. By using QOLB synchronization primitives, the next processor can be determined at the execution time. We prove that the selective write-update protocol ensures data coherency of parallel programs that comply with release consistency, and evaluate the performance of the protocol by analytical modeling and program-driven simulation. The simulation results show that our protocol can reduce the number of coherence misses in a critical section while avoiding the multicast of write-update requests on an interconnection network. In addition, we observe that synchronization latency can be decreased by reducing both the execution time of a critical section and the number of write-update requests. From the simulation results, it is shown that our protocol provides better performance than a write-invalidate protocol and a write-update protocol as the number of processors increases.

A convenient signaling scheme, termed orthogonal on-off BPSK (O3BPSK), along with a simple one-shot linear decorrelating detector (LDD) has been proposed by Zheng and Barton as a technique for near-far resistant detection in the asynchronous DS/CDMA systems. The temporally adjacent bits from different users in the received signals are decoupled by using the on-off signaling, and the data rate is maintained with no increase in transmission rate by adopting an orthogonal structure. The system performance of this signaling scheme in terms of bit error rate (BER) has been analyzed over an AWGN channel by Zheng and Barton. In this paper, we further study the system performance over Nakagami-m fading channel. A closed form for the BER of such a scheme is successfully derived. Numerical results show that the O3BPSK signal scheme along with the LDD receiver still offers a good near-far resistant property over Nakagami-m channel.

DQRUMA (Distributed-Queueing Request Update Multiple Access) protocol has been proposed as an access protocol for the wireless ATM Local Area Networks. DQRUMA protocol is useful to transmit fixed-length packets (e. g. ATM cells). However, it cannot be applied to multimedia environment because it does not include any access control policy for multimedia traffic. In the paper, we propose a slot assignment scheme of DQRUMA protocol in wireless ATM LAN which supports integrated multimedia traffic with different service requirements. In this scheme we can allocate network resources according to the service requirements of each medium because the base station assigns Transmit-Permission flexibly according to the features of each medium.

As the current Internet becomes popular in information access, demands for real-time display and playback of continuous media are ever increasing. The applications include real-time audio/video clips embedded in WWW, electronic commerce, and video-on-demand. In this paper, we present a new control protocol R3CP for real-time applications that transmit stored MPEG video stream over a lossy and best-effort based network environment like the Internet. Several control mechanisms are used: a) packet framing based on the meta data; b) adaptive queue-length based rate control scheme; c) data preloading; and d) look-ahead pre-retransmission for lost packet recovery. Different from many adaptive rate control schemes proposed in the past, the proposed flow control is to ensure continuous, periodic playback of video frames by keeping the receiver buffer queue length at a target value to minimize the probability that player finds an empty buffer. Contrary to the widespread belief that "Retransmission of lost packets is unnecessary for real-time applications," we show the effective use of combining look-ahead pre-retransmission control with proper data preloading and adaptive rate control scheme to improve the real-time playback performance. The performance of the proposed protocol is studied via simulation using actual video traces and actual delay traces collected from the Internet. The simulation results show that R3CP can significantly improve frame playback performance especially for transmission paths with poor packet delivery condition.

Because of non-negligible ISI due to the Gaussian filter and delay spread in the GSM system, an equalizer is required. In this letter, a joint sliding window channel estimation and timing adjustment method is proposed for maximum likelihood sequence equalizer. And also a smoothing algorithm is presented in order to improve the equalizer performance. This smoothing scheme utilizes a variant of LMS algorithm to tune the channel coefficient estimates. Simulation results show that the proposed scheme is adequate for channel estimation of the adaptive equalizer.

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.

A new type of a linear decorrelating receiver, named Pseudo-Decorrelator, for asynchronous code division multiple access systems over an additive white Gaussian noise channel is presented in this paper. Starting with the analyis of the multiple access components of the decision statistics, the outputs of a bank of matched filters, the (K 3K) cross-correlation matrix for each bit is obtained. The non-square cross-correlation matrix is then inverted using the concept of Penrose's generalized inverse of a matrix. In this receiver, the detection process can be started before the whole sequence is received at the receiver, and computing the inverse of a (KN KN) cross-correlation matrix, generally required for linear decorrelating receivers, can be avoided because it is enough to compute only the generalized inverse of a (K 3K) cross-correlation matrix for each data bit. Here, K is the number of users and N is the length of input data sequence. Simulation results are also presented for K-user systems over an additive white Gaussian noise channel.

In this paper, Orthogonal Multicode OFDM-DS/CDMA system using Partial Bandwidth Transmission is proposed. By using the flexible carrier allocation of OFDM, Partial Bandwidth Transmission is considered for high quality communication. Furthermore, multicode packet data transmission is presented. Multicode packet data transmission is very effective to handle variable data. Since the proposed system can detect the header information without complex control, it is also suitable for packet data transmission. The computer simulation results show that the BER performance of the proposed system with the ideal channel estimation is improved compared with the case of the conventional Orthogonal Multicode DS/CDMA system with ideal RAKE receivers. Moreover the proposed system with the channel estimation by MLS algorithm also shows the good BER performance. In packet data transmission, the delay and throughput performances are also improved in the proposed system.

A highly reliable and highly efficient fuel-cell energy system is being developed that can run on various fuels and is suitable for a cogeneration system for telecommunications facilities. In this system, electrical power supplants the mains power and heat energy is used for air conditioning. Using this fuel-cell power plant as an emergency generator and ensuring the reliability of telecommunications requires the use of alternate fuels. This plant can run on liquefied petroleum gas(LPG)if the pipeline gas supply stops. Fuel substitution characteristics, and DC and AC interconnection characteristics have been experimentally demonstrated for connections by using a 200-kW phosphoric acid fuel cell and a 150-kW engine generator.

This paper proposes local lightwave networks with grouping property which are based on a wavelength division multiplexing (WDM). The proposed network is partitioned into several groups according to traffic volume between stations so that traffic is more likely to be within groups. The stations within a group are connected to a broadcast-and-select WDM network with star topology. For inter-group communication, a WDM network of each group is connected to another star-topology WDM network through a special station called a router. In the proposed network, intra-group communication is achieved by one hop and inter-group communication goes through multiple hops. We analyze the average hop number, the maximum throughput, and the mean packet delay of the proposed network and investigate its performance characteristics. Since the proposed network has the better performance as its grouping property strengthens, it is fit for local lightwave networks with the locality of traffic.