We apply Fahlman and Lebiere's (FL) algorithm to network synthesis and incremental learning by making use of already-trained networks, each performing a specified task, to design a system that performs a global or extended task without destroying the information gained by the previously trained nets. Investigation shows that the synthesized or expanded FL networks have generalization ability superior to Back propagation (BP) networks in which the number of newly added hidden units must be pre-specified.

Kleene-Stone algebra is both Kleene algebra and Stone algebra. The set of Kleene-Stone logic functions discussed in this paper is one of the models of Kleene-Stone algebra, and they can easily represent the concepts of necessity and possibility which are important concepts for many-valued logic systems. Main results of this paper are that the followings are clarified: a necessary and sufficient condition for a function to be a Kleene-Stone logic function and a formula representing the number of n-variable Kleene-Stone logic functions.

In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x{0,1}*, outputs y such that (x,y)R with overwhelming probability if xdom R, and outputs "" with probability 1 if x dom R. The result above can not be generalized to zero-knowledge interactive proof systems of possession of knowledge with more than four moves, because it is known that there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of possession of knowledge for a nontrivial relation R.

In this paper, we propose an extended LR parsing algorithm, called LR parsing with a category reachability test (the LR-CRT algorithm). The LR-CRT algorithm enables a parser to efficiently recognize those sentences that belong to a specified grammatical category. The key point of the algorithm is to use an augmented LR parsing table in which each action entry contains a set of reachable categories. When executing a shift or reduce action, the parser checks whether the action can reach a given category using the augmented table. We apply the LR-CRT algorithm to improve a speech recognition system based on two-level LR parsing. This system uses two kinds of grammars, inter- and intra-phrase grammars, to recognize Japanese sentential speech. Two-level LR parsing guides the search of speech recognition through two-level symbol prediction, phrase category prediction and phone prediction, based on these grammars. The LR-CRT algorithm makes possible the efficient phone prediction based on the phrase category prediction. The system was evaluated using sentential speech data uttered phrase by phrase, and attained a word accuracy of 97.5% and a sentence accuracy of 91.2%

In this paper a recursive form of Welch-Berlekamp (W-B) algorithm is provided which is a novel and fast decoding algorithm.

The demand for mobile communications is continuing to grow, but there is a limit on the radio frequency resources. Micro cellular systems are a strong solution to this problem. However, Forced Call Termination (FCT) and Channel Changing (CC) occur frequently in these systems because of their small cell size. This paper proposes a new Dynamic Channel Assignment (DCA) strategy which uses information of moving direction of Mobile Stations (MSs) to reduce FCT and CC. This strategy, the MD (Moving Direction) strategy, is compared with other major DCA strategies by simulating a one-dimensional service area covering a road, such as an expressway. The simulation shows that the MD strategy performs better than the other strategies with regard to FCT, CC, and carried load. FCT is an especially important factor in the quality of service. The MD strategy reduces FCT and has the largest carried load of the strategies, which means that it has the most efficient channel usage. This is an attractive characteristic of the MD strategy for micro cellular systems.

An adaptive fuzzy network (AFN) is described that can be used to implement most of fuzzy logic functions. We introduce a learning algorithm largely borrowed from backpropagation algorithm and train the AFN system for several typical fuzzy problems. Simulations show that an adaptive fuzzy network can be implemented with the proposed network and algorithm, which would be impractical for a conventional fuzzy system.

This is a partly expository paper discussing how point processes with certain "bursty" features can be qualitatively modelled by the Markovian arrival process, a generalization of the Poisson or Bernoulli processes which can be used to obtain algorithmically tractable matrix solutions to a variety of problems in probability models.

For the connection request procedure in mobile communication systems, a previous study had shown that the 3-channel systems provide the haighest maximum of stable per channel throughput. In this paper, we propose and study a new algorithm, called the Parallel Collision Resolution Algorithm, which can be implemented in a Q-channel connection request environment, where Q3. For the implementation, the channels are arranged in R groups, where R is a positive integer. The collision resolution scheme distributes the collided messages over all the groups so that throughput and delay measures can be improved. At any point in time, there can be a maximum of R collision resolution schemes operational irrespective of the channel or the group number over which collisions occurred. The performance measures are estimated by computer simulation. Under the new algorithm, almost the same level of the perchannel stable throughput measure of a 3-channel network can be achieved in networks for which Q3. This feature allows freedom to the network designer to employ a higher number of connection request channels without forfeiting high channel utilization rates. When Q is an integral multiple of 3, the maximum stable per channel throughput level achieved can be the same as that achieved by the 3 channel system, if the grouping of channels is such that each group consists of 3 channels. When Q is not an integral multiple of 3, the intuitive strategy of organizing the channels in such a way that Q/3 groups consist of 3 channels each and one group consists of (Q mod 3) channels, may result in much degraded performance. It is found that, if the channels are so organised that no group is composed of (Q mod 3) channels, the performance levels can be substantially enhanced. Also, under the new algorithm, the delay measure is significantly improved, particularly in schemes like the mobile satellite systems with high propagation delays. We conclude that the new scheme presents a promising collision resolution methodology for connection request procedures.

A multicast error control protocol proposed by Metzner is generalized and the performance of the proposed protocol on random error channels (binary symmetric channels) is analyzed. The proposed protocol adopts an encoding procedure based on a product code structure, whith enables each destined user terminal to decode the received frames with the Reddy-Robinson algorithm. As a result, the performance degradation due to the re-broadcasting of the replicas of the previously transmitted frames can be circumvented. The numerical results for the analysis and the simulation indicate that the proposed protocol yields higher throughput and less degradation of throughput with an increase of the number of destined terminals.

This paper proposes a new adaptive algorithm for acoustic echo cancellers with four times the convergence speed for a speech input, at almost the same computational load, of the normalized LMS (NLMS). This algorithm reflects both the statistics of the variation of a room impulse response and the whitening of the received input signal. This algorithm, called the ESP (exponentially weighted step-size projection) algorithm, uses a different step size for each coefficient of an adaptive transversal filter. These step sizes are time-invariant and weighted proportional to the expected variation of a room impulse response. As a result, the algorithm adjusts coefficients with large errors in large steps, and coefficients with small errors in small steps. The algorithm is based on the fact that the expected variation of a room impulse response becomes progressively smaller along the series by the same exponential ratio as the impulse response energy decay. This algorithm also reflects the whitening of the received input signal, i.e., it removes the correlation between consecutive received input vectors. This process is effective for speech, which has a highly non-white spectrum. A geometric interpretation of the proposed algorithm is derived and the convergence condition is proved. A fast profection algorithm is introduced to reduce the computational complexity and modified for a practical multiple DSP structure so that it requires almost the same computational load, 2L multiply-add operations, as the conventional NLMS. The algorithm is implemented in an acoustic echo canceller constructed with multiple DSP chips, and its fast convergence is demonstrated.

This paper presents a new architecture of a copy network which employs the principle of recursive generation of copy cells. The proposed architecture achieves high utilization of the links and buffers of the copy network, and preserves the cell sequence. The architecture lends itself modularity so that large multicast ATM switches can be fabricated by employing the proposed copy network. Two different modular structures - one for reduced latency of the unicast cell and the master cell from which copies are made, and the other for reduced hardware overhead - for realizing large multicast ATM switches are configured. The hardware of functional elements of the copy network are the same as those of the functional elements of a modular point-to-point switch proposed earlier, thereby resulting in the modularity of functional elements as well. Simulation studies show that the proposed copy network achieves high throughput and low cell loss probability, and the required buffer sizes are small. The delay of cells is found to be very small for traffic loads up to 90%.

This paper relates to a novel algorithm for fast estimation of the coefficients of the adaptive FIR filter. The novel algorithm is derived from a first order IIR filter experssion clarifying the estimation process of the NLMS (normalized least mean square) algorithm. The expression shows that the estimation process is equivalent to a procedure extracting the cross-correlation coefficient between the input and the output of an unknown system to be estimated. The interpretation allows to move a subtraction of the echo replica beyond the IIR filter, and the movement gives a construction with the IIR filter coefficient of unity which forms the arithmetic mean. The construction in comparison with the conventional NLMS algorithm, improves the covergence rate extreamly. Moreover, when we use the construction with a simple technique which limits the term of calculating the correlation coefficient in the beginning of a convergence process, the convergence delay becomes negligible. This is a very desirable performance for acoustic echo canceller. In this paper, double-talk and echo path fluctuation are also studied as the first stage for application to acoustic echo canceller. The two subjects can be resolved by introducing two switches and delays into the evaluation process of the correlation coefficient.

An efficient reconstruction algorithm for diffraction tomography based on the modified Newton-Kantorovich method is presented and numerically studies. With the Fréchet derivative obtained for the Helmholtz equation, one can derive an iterative formula for getting an object function, which is a function of refractive index of a scatterer. Setting an initial guess of the object function to zero, the pth estimate of the function is obtained by performing the inverse Fourier transform of its spectrum. Since the spectrum is bandlimited within a low-frequency band, the algorithm does not require usual regularization techniques to circumvent ill-posedness of the problem. For numerical calculation of the direct scattering problem, the moment method and the FFT-CG method are utilized. Computer simulations are made for lossless and homogeneous dielectric circular cylinders of various radii and refractive indices. In the iteration process of image reconstruction, the imaginary part of the object function is set to zero with a priori knowledge of the lossless scatterer. Then the convergence behavior of the algorithm remarkably gets improved. From the simulated results, it is seen that the algorithm provides high-quality reconstructed images even for cases where the first-order Born approximation breaks down. Furthermore, the results demonstrate fast convergence properties of the iterative procedure. In particular, we can successfully reconstruct the cylinder of radius 1 wavelength and refractive index that differs by 10% from the surrounding medium. The proposed algorithm is also effective for an object of larger radius.

In this paper we present and analyze multi-level quorum schemes for maintaining the consistency of replicated data in the presence of concurrency and failures in a large distributed environment. The multi-level quorum method operates on a logical hierarchy of the nodes in the network and applies well known flat voting algorithms for replicated data concurrency control in a layered fashion. We show how the number of hierarchy levels, the number of logical entities per level and the voting algorithms used on each level affect the costs and the degree of availability associated with a wide range of multi-level quorum schemes. The results of the analysis are used to provide guidelines for designing the most suitable multi-level quorum strategy for a given application scenario. Comparative performance measurements in a simulated network are presented to illustrate the properties of multi-level approaches when some of the assumptions of the analytical investigation do not hold.

There have been few studies on formal approaches to the specification and realization of asynchronous sequential circuits. For synchronous sequential circuits, an algebraic method is proposed as one of such approaches, but it cannot be applied to asynchronous ones directly. This paper describes an algebraic method of specifying the abstract behavior of asynchronous sequential circuits. We select an daisy chain arbiter as an example of them. In the arbiter, state transitions are caused by input changes, and all the modules do not always make state transitions simultaneously. These are main obstacles to specify it in the same way as sychronous sequential circuits. In order to remove them, we modify the meaning of input in specifications and introduce pseudo state transitions so that we can regard all the modules as if they make state transitions simultaneously. This method can be applied to most of the other asynchronous sequential circuits.

Fahlman and Lebiere's (FL) learning algorithm begins with a two-layer network and in course of training, can construct various network architectures. We applied FL algorithm to the same three-layer network architecture as a back propagation (BP) network and compared their generalization properties. Simulation results show that FL algorithm yields excellent saturation of hidden units which can not be achieved by BP algorithm and furthermore, has more desirable generalization ability than that of BP algorithm.

This paper presents a protocol verification method which verifies that the behaviors of a protocol meet requirements. In this method, a protocol specification is expressed as Extended Finite State Machines (EFSM's) that can handle variables, and requirements are expressed using a branching-time temporal logic for a concise and unambiguous description. Using the acyclic expansion algorithm extended such that it can deal with EFSM's, the verification method first generates a state transition graph consisting of executable transitions for each process. Then a branching-time temporal logic formula representing a requirement is evaluated on one of the generated graphs which is relevant to the requirement. An executable state transition graph for each process is much smaller than a global state transition graph which has been used in the conventional verification techniques to represent the behaviors of the whole protocol system consisting of all processes. The computation for generating the graphs is also reduced to much extent for a large complex protocol. As a result, the presented method achieves efficient verification for requirements regarding a state of a process, transmission and reception of messages by a process, varibales of a process and sequences that interact among processes. The validity of the method is illustrated in the paper by the verification of a path-updating protocol for requirements such as process state reachability or fair termination among processes.

The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect M , X and PN (a sequence of transitions, with the first transition firable on M , such that every transition t can fire prescribed number X(t) of times). The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.

The subject of the paper is to propose two approximation algorithms FM_SPLA, FM_DPLA for priority-list scheduling in timed Petri nets. Their capability is compared with that of existing algorithms SPLA, DPLA through experimental results, where SPLA and DPLA have previously been proposed by the authors.