In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by 1 in the protocol. These results suggest that, even when all channeles in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the channel capacity 0 does not allow protocols to transmit and recieve messages.

This letter discusses a relation between reliability and network topology of starred polygon with redundant nodes. Each node of starred polygon is augmented by a spare node, and the degree of survivability is newly defined to evaluate reliability. The main result presents three special topologies of starred polygon with redundant nodes that realize an optimal degree of survivability.

This paper describes new modeling methods combining neural network and hidden Markov model applicable to modeling a time series such as speech signal. The idea assumes that the sequence is nonstationary and is a nonlinear autoregressive process whose parameters are controlled by a hidden Markov chain. One is the model where a non-linear predictor composed of a multi-layered neural network is defined at each state, another is the model where a multi-layered neural network is defined so that the path from the input layer to the output layer is divided into path-groups each of which corresponds to the state of the Markov chain. The latter is an extended model of the former. The parameter estimation methods for these models are shown, and other previously proposed models--one called Neural Prediction Model and another called Linear Predictive HMM--are shown to be special cases of the NPHMM proposed here. The experimental result affirms the justification of these proposed models.

To provide the processor arrays with adequate fault-tolerant capabilities, a number of spare or redundant processors are prepared within the arrays. For such processor arrays, reconfiguration should be executed to bypass faulty processors. Concerning reconfiguration of processor arrays, Melhem presented a minimization problem (called the SPA problem). The SPA problem is to find an assignment of spare processors to faulty processors that minimizes the number of dangerous processors. Here, the dangerous processors are processors, for which there remains no longer any spare processor to be assigned when one more faults occur. In this paper, we present a more rigorous definition of the SPA problem, in which input parameters are n2 ordinary processors, 2n spare processors and m (mn2) faulty processors, and the output is an optimal assignment of spare processors to faulty processors, in the sense that the number of dangerous processors is minimum. Then, we develop an efficient algorithm based on the necessary and sufficient conditions, which allows highly efficient computation of spare processor assignment. The worstcase time complexity of the proposed algorithm is O(n2).