A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict. A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by strict droca's is a subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidablity of the equivalence problem for strict droca's is obvious. In this paper, we present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by strict droca's. Then we show that the worst-case time complexity of our algorithm is polynomial with respect to these automata.

This paper studies congestion control schemes for integrated variable bit-rate (VBR) video and data communications, where the quality of service (QOS) of each medium needs to be satisfied. In order to control congestion, we exert here either dynamic resolution control or QOS control. The dynamic resolution control scheme in this paper dynamically changes the temporal or spatial resolution of video according to the network loads. The QOS control scheme here assigns a constant capacity of buffer to each connection and determines the video resolution in order to guarantee the QOS of each medium at the connection establishment. The performance of these schemes is evaluated through simulation in terms of throughput, video frame delay probability distribution, and video frame loss rate. We also examine the effects of priority scheduling and packet discarding on the performance. Numerical results indicate that both dynamic resolution and QOS control attain low delay jitters as well as large video and data throughput. In particular, the QOS control is shown to be more suitable for integrated VBR video and data communications.

This paper proposes a novel updating technique, dynamically updating, for achieving extension or modification of functions in a distributed system. Usual updating technique requires synchronous suspension for multiple processes for avoiding unspecified reception caused by the conflict of different versions of processes. Thus, this technique needs very high overhead and it must restrict the types of distributed systems, to which it can be applied, to RPC (remote procedure call) type or client-server type. Using the proposed dynamically updating technique, updating management can be invoked asynchronously by each process with assurance of correct execution of the system, i.e., the system can cope with the effect of unspecified reception caused by mixture of different version processes. Therefore, low overhead updating can be achieved in partner type distributed systems, that is more general type including communications systems or computer networks. Dynamically updating technique is implemented by using a novel distributed algorithm that consists of group communication, checkpoint setting, and rollback recovery. By using the algorithm proposed in this paper, rollback recovery can be achieved with the lowest overhead, i.e., a set of checkpoint determines the last global state for consistent rollback recovery and a set of processes that need to rollback simultaneously is the smallest one. This paper also proves the correctness of the proposed algorithm.

Optical path technology that employs both WDM/FDM and wavelength routing will play a key role in supporting future high bandwidth transport networks. WP/VWP (Wavelength Path/Virtual Wavelength Path) technologies are very effective in realizing optical path networks. In these networks, since photonic wavelengths are scarce resources, the number of wavelengths required to construct the network must be minimized. However, the wavelength assignment problem, minimizing the number of wavelengths, is an NP-complete problem. Solving this problem heuristically is an important issue for designing large-scale WP/VWP based networks that are also practical. To realize optical path networks, we need to develop path accommodation design algorithms that heuristically solve the wavelength assignment problem. This paper proposes novel path accommodation design algorithms for WP/VWP networks that minimize the number of wavelengths required. We numerically elucidate that the numbers of wavelengths required for active WPs and VWPs are almost equal. When link failure restoration is considered, they are different; more wavelengths are needed with the WP scheme than with the VWP scheme. It is also demonstrated that the proposed algorithms are applicable to a large scale network design.

In this paper, we propose a new framework for global traffic control in ATM networks which aims to maximize resource utilization and to guarantee the reliable congestion control. To do this, we first propose Global Traffic Control (GTC) mechanism which is based on harmonious cooperation of each traffic control function. GTC measures real bandwidth utilization to compensate inaccuracy of the declared mean cell rate and it also monitors cell losses to manage input traffic load when a network approaches congestion state. We also propose new adaptive connection admission control (CAC) algorithms which calculate cell loss performance of related function blocks in a switch node using only a declared peak cell rate and an estimated mean cell rate. We measure only the mean cell rate of the aggregate cell stream in a link to estimate the mean cell rate of each virtual channel connection. We adopt a peak cell rate spacer at the User Network Interface (UNI) to compensate a cell delay variation (CDV). We will also present an approximation technique to estimate a queue length distribution of a general queue. As this technique requires negligible calculation time, it can meet the stringent requirement on the connection set-up time.

Data communication by using TCP/IP is one of important services on ATM networks. At one approach in traffic control of this service, the dedicated bandwidth for data transfer is not guaranteed and the feedback congestion control to prevent cell loss is performed in the congestion case. However, when a large quantity of data is transferred within a short period, this traffic control cannot be expected to achieve high efficiency. In this case, it is suitable that the dedicated bandwidth is guaranteed by FRP (Fast Reservation Protocol) before the data is transferred. This paper describes that FRP is superior to the feedback congestion control for large size data transmission. Next, it proposes a selectable traffic control which selects adaptively one of the feedback congestion control and FRP.

Board-to-board signal transmission in a rack system is affected by various types of noise. Signal transmission capability is evaluated on the basis of physical construction parameters and signal conditions, such as rise time and amplitude. This paper examines noise in a rack system and shows that the maximum single-ended transmission capability is 100Mbps when pin-type connectors are used with a signal/ground pin assignment ratio of 1/1.

The Distributed Queue Dual Bus protocol (DQDB) has been adopted as the metropolitan area network (MAN) standard by IEEE802.6 committee. Recently, the unfairness problem in the DQDB protocol, by which head stations benefit, has been pointed out. Although a fair bandwidth distribution among the stations is obtained by adding the so-called bandwidth balancing mechanism into the DQDB protocol (DQDB/BB), the DQDB/BB protocol leaves a portion of the available bandwidth unused, and it takes a considerable amount of time to converge to fair channel assignment. In this study, to overcome the drawbacks in DQDB and DQDB/BB, we introduce a new media access control protocol which is based on assigning each station a level according to some traffic information such as the queueing length, delay time etc. Only the station with the highest level is allowed to transmit. Through the operation of level assignment or the choice of level function, the transmission can be easily controlled in a distributed manner. This protocol is simple compared with DQDB/BB and can be implemented in the DQDB architecture. The simulation results show that the new protocol obtains not only fair throughput regardless of the distance between the stations, but also fair delay performance. In addition, the new protocol can easily provide preempty priority service through level assignment. The new protocol converges to fair distribution of the channel in the time required for only one or two round-trips. This is very fast compared with the DQDB/BB protocol.

A number of flexible control mechanisms used in buffer management, congestion control and bandwidth allocation have been proposed to improve the performance of ATM networks by introducing parameters, such as threshold, push-out probability and incremental bandwidth size of a virtual path, which are adjustable by network providers. However, it is difficult to adaptively adjust these parameters, since the traffic in ATM networks is further complicated by accommodating various kinds of services. To overcome the problem, we propose in this paper a control scheme based on the genetic algorithms and the neural estimator. The neural estimator forecasts the future QOS values for each candidate parameter set, and the genetic algorithms select the best one to control the real network. An example of buffer management in an ATM switch is examined in this paper. Simulation results show the effectiveness of the proposed control scheme in adaptively adjusting the parameter set even when the traffic environment and the QOS requirements are dynamically changing.

The recent progress of B-ISDN signaling systems has enabled networks to handle calls which require a wide variety of ATM connection sets. This paper is concerned with the circuit group which handles calls requesting asymmetric forward and backward multi-connections, and has the capability of both bandwidth negotiation and bandwidth reservation as a traffic control for enhancing call blocking performance. A model of the circuit group is first established focusing on the call level characteristics of the group, and then a method based on the reduced load approximation and an approximate analysis of a multirate group is proposed for calculating approximate blocking probabilities. The accuracy of the approximation method is evaluated numerically by comparing with an exact method and simulation. Further the impact of bandwidth negotiation and reservation on call blockings is examined based on numerical examples.

This paper discusses two approaches to statistical multiplexing: rate envelope multiplexing, allowing resource sharing with small delays for low peak rate connections, and rate sharing, based on the use of large multiplexer buffers to ensure high link utilization for high speed data traffic. We argue that the weighted fair queueing scheduling algorithm provides an efficient means for combining both kinds of multiplexing in the B-ISDN. A feasible implementation known as Virtual Spacing is outlined. We illustrate the flexibility of the proposed scheme by showing how different service categories could be provided.

This paper presents an experimental result of polarimetric detection of objects buried in a sandy ground by a synthetic aperture FM-CW radar. Emphasis is placed on the reduction of surface clutter by the polarimetric radar, which takes account of full polarimetric scattering characteristics. First, the principle of full polarimetric imaging methodology is outlined based on the characteristic polarization states for a specific target together with a polarimetric enhancement factor which discriminates desired and undesired target echo. Then, the polarimetric filtering technique which minimizes a surface reflection is applied to detect a thin metallic plate embedded in a sandy ground, demonstrating the potential capability of reducing surface clutter which leads to an improvement of underground radar performance, and validating the usefulness of FM-CW radar polarimetry.

This paper describes reverse modulation carrier recovery with a tank-limiter for Offset QPSK (OQPSK) burst signals. Acquisition performance is discussed taking into account hardware implementation errors in the carrier recovery circuit. The results indicate hardware implementation errors cause a significant recovered carrier phase error during BTR (Bit Timing Recovery) of OQPSK burst signals. A phase error reduction technique by modifying the BTR code for OQPSK burst signals is proposed to improve the acquisition performance. Computer simulation and hardware experiments confirmed its improvement. The performance of a prototype OQPSK burst demodulator using the proposed carrier recovery scheme is also presented.

A uniquely-structured Usage Parameter Control (UPC) method named Virtual-shaping is proposed which considers cell arrival time jitter between user and UPC point. The method uses a modified Dangerous Bridge UPC circuit (Sliding window type) and virtually (logically) shapes cell traffic using cell arrival time compensation to offset cell delay variation (CDV). In addition, the proposed method is based on a cell-buffer-less structure and can be realized with reasonable hardware. The method yields precise and accurate monitoring. Computer simulations show that the method offers higher network utilization than the conventional Leaky Bucket based UPC method. The proposed method will make it possible to create more effective B-ISDNs, and more cost-effective broadband VBR services.

We investigated performance of routing schemes in B-ISDN, for heterogeneous traffic flows under various bandwidths. In particular, we compared the simulated performance of these schemes by evaluating their blocking probabilities. To achieve high performance, these schemes use special kinds of routing algorithm, one which is pre-selection algorithm and one which is cyclic algorithm. We investigated the efficiency of the pre-selection algorithm and the robustness of the cyclic algorithm for nonuniform traffic and network resources. We found that these routing algorithm schemes can compensate for errors in resource design.

A new gloss-extracting method is proposed in this study. A spatial filter with variable resolution is used for the extraction of glossiness. Various spheres and cylinders with curvature radii from 4 to mm are used as the specimens. In all samples, a strong correlation, with a correlation coefficient of more than 0.98, has been observed between psychological glossiness Gph perceived by the human eye and glossiness Gfm extracted by this method. This method is useful for plane specimens as well as spherical and cylindrical ones.

This paper describes an O(log3n) time O(n/log n) processors parallel algorithm for determining the congruence (exact matching) of two point sets in three-dimensions on a CREW PRAM, where n is the maximum size of the input point sets. Although optimal O(n log n) time sequential algorithms were developed for this problem, no efficient parallel algorithm was known previously. In the algorithm, the original problem is reduced to the two-dimensional congruence problem by computing a three-dimensional point set cps(S) for each input point set S, where cps(S) satisfies the following conditions: 0|cps(S)|12; cps(T(S))T(cps(S)) for all isometric transformations T. The two-dimensional problem can be solved efficiently in parallel using a parallel version of a previously-known sequential algorithm. cps(S) is computed recursively in the following way: the size of a point set is reduced by a constant factor in each recursive step. To reduce the size of a point set, a convex hull is constructed and then it is regarded as a planar graph, so that combinatorial properties of a planar graph are used effectively. A sequential version of the algorithm works in O(n log n) time, so that this paper gives another optimal sequential algorithm. The presented algorithm can be applied for graphs such that each vertex corresponds to a point and each edge corresponds to a line segment connecting its endpoints. Moreover, the algorithm can be modified for computing the canonical form of a point set or a graph.

This paper proposes a hybrid access control scheme for broadcast-based ATM-LANs. Broadcast-based ATM-LANs are shared media networks with star topology. In this network, packets are broadcast to all subscriber terminals by a CPYF (Cell COPY Function) node located in the ATM network and only relevant packets are extracted and sent to the destined user layer function by packet filtering functions in the terminals. The simplicity of the packet transfer mechanism makes the network very economical. In broadcast-based ATM-LANs, the hybrid access control scheme is effective in improving performance. In this scheme, short packets and long packets are transmitted respectively by means of a back-pressure type and a CSMA/CD type access control scheme. Throughput evaluation was performed by computer simulation and the results show that the proposed scheme achieves a high throughput characteristic.

In this study, we investigate the synchronization phenomena of coupled Wien bridge oscillators. The oscillator is characterized by a voltage controlled resistor with saturation. We use linear resistance to couple the oscillators. Two different kinds of coupling techniques, called current and voltage connections are proposed and they show completely opposite mode of synchronized oscillations. The dynamics of the two circuits are also derived to study the amplitude and phase dynamics of the synchronized state. The current connection has a simple resistive effect but stable phase mode is opposite to that of the voltage connection. The voltage connection has the coupling effect which is a combination of resistive and reactive couplings. Coupled three oscillators with current and voltage connection are also studied and stable tri-phase and in-phase synchronizations are observed, respectively. Averaging method is used to investigate the stability of synchronized mode of oscillations. Experimental results are also stated which agree well with the theory.

In this paper, we present a method for extracting the Japanese printed characters from unformatted document images. This research takes into account the multiple general features specific to the Japanese printed characters. In our method, these features are thought of as the constraints for the regions to be extracted within the constraint satisfaction approach. This is achieved by minimizing a constraint function estimating quantitative satisfaction of the features. Our method is applicable to all kinds of the Japanese documents because it is no need of a priori knowledge about the document layout. We have favorable experimental results for the effectiveness of this method.