This paper reports computational results of a new approach of analyzing network reliability against probabilistic link failures. This problem is hard to solve exactly when it is large-scale, which is shown from complexity theory, but the approach enables us to analyze networks of moderate size, as demonstrated by our experimental results. Furthermore, this approach yields a polynomial-time algorithm for complete graphs, whose reliability provides a natural upper bound for simple networks, and also leads to an efficient algorithm for computing the dominant part of the reliability function when the failure probability is sufficiently small. Computational results for these cases are also reported. This approach thus establishes a fundamental technology of analyzing network reliability in practice.

We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)^α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.

Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.

We show that the permanent of an m n rectangular matrix can be computed with O(n 2^m 3^m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log₃ 2 and n .

This paper introduces an alternating rebound Turing machine and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any o(log n) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any o(logn) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log n. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by o(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene .

A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (f : {0,1}ⁿ Z). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within n^O(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.

For given undirected graph G[V,E] and vertices s and t, a minimal s-t separating set denoted by E_c & V_c is a minimal set of elements (edges and/or vertices) such that deletion of the elements from G breaks all the paths between s and t, where E_c and V_c are sets of edges and vertices, respectively. In this paper, we consider a problem of generating all minimal s-t separating sets, and show that the problem can be solved in O(µ(mt(n,n))) time, where m|E|, n|V|, µ is the number of minimal s-t separating sets of G, and t(p,q) is the time needed for finding q lowest common ancestors for q pairs of vertices in a rooted tree with p vertices. Since t(n,n) can be O(n), we can generate all minimal s-t separating in linear time per s-t separating set. However, the linear time algorithm for finding the lowest common ancestors is complicated, so that it is not efficient for a moderate size graph. Therefore, we use an O(nα (n))-time algorithm for finding the lowest common ancestors, and propose an algorithm to generate all minimal s-t separating sets in O(mnα(n)) time per s-t separating set, where α(n) is the pseudo-inverse of Ackermann function.

All-terminal reliability is one of the measurements to evaluate the reliability for network systems. Since it may need exponential time of the network size to compute the exact value of all-terminal reliability, it is important to calculate its tight approximate value, especially its lower bound, at a moderate calculation time. Ramanathan and Colbourn have proposed approaches for lower bounds of all-terminal reliability by using arc-packings but their approaches are not detailed enough to construct concrete algorithms and they have just evaluated their approaches for a particular network. In this paper, we construct concrete algorithms based on their approaches and suggest new algorithms. We also execute computational experiments for general networks in order to evaluate the lower bounds by the algorithms and show the effectiveness of our new algorithms.

This paper proposes the UGLR parser as an extension of the GLR parser. A UGLR parser is powerful enough to parse deterministically any phrase structure language if it is in the class of recursive languages and can parse any context free language as fast as the conventional GLR parser. Natural language processing often requires a parser for languages belonging to classes larger than that of context free languages, and the proposed parser is useful for this purpose.

This paper presents a new approach to designing arithmetic circuits by using a graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG). The key idea of the proposed method is to introduce a higher level of abstraction for arithmetic algorithms, in which arithmetic circuit structures are modeled as data-flow graphs associated with specific number representation systems. The EGG system employs evolutionary operations to transform the structure of graphs directly, which makes it possible to generate the desired circuit structure efficiently. The potential capability of EGG is demonstrated through an experiment of generating constant-coefficient multipliers.

In this paper we study n-input m-output Boolean functions (abbr. (n,m)-functions) with high nonlinearity. First, we present a basic construction method for a balanced (n,m)-function based on a primitive element in GF(2^m). With an iterative procedure, we improve some lower bounds of the maximum nonlinearity of balanced (n,m)-functions. The resulting bounds are larger than the maximum nonlinearity achieved by any previous construction method for (n,m)-functions. Finally, our basic method is developed to construct an (n,m)-bent function and discuss its maximum algebraic degree.

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

In this paper, the Lapped Orthogonal Transform (LOT) with unequal length basis function is considered. The proposed unequal length LOT (ULLOT) has both long basis of length 2M and short basis of length M, while the lengths of all bases of the conventional LOT are 2M. A new class of LOT can be constructed with some modifications of Malvar's Fast LOT. Therefore, the fast algorithm for the Discrete Cosine Transform (DCT) will surely facilitate the computation of the ULLOT. Although the computational complexity of the ULLOT is always lower than that of the LOT, there exist some cases where the coding gain of the ULLOT becomes slightly higher than that of the LOT. Its ability to reduce ringing artifacts is an attractive feature as well. The size-limited structure for the finite length signal is investigated and the ULLOTs are tested on image coding application. The simulation results confirm the validity of the proposed ULLOT.

Following our former works on regular sampling in wavelet subspaces, the paper provides two algorithms to estimate the truncation error and aliasing error respectively when the theorem is applied to calculate concrete signals. Furthermore the shift sampling case is also discussed. Finally some important examples are calculated to show the algorithm.

This paper presents an efficient algorithm to compute the characteristic polynomial of a polynomial matrix. We impose the following condition on given polynomial matrix M. Let M₀ be the constant part of M, i. e. M₀ M ( mod (y,,z)), where y,,z are indeterminates in M. Then, all eigenvalues of M₀ must be distinct. In this case, the minimal polynomial of M and the characteristic polynomial of M agree, i. e. the characteristic polynomial f(x,y,,z) | x E M | is the minimal degree (w. r. t. x) polynomial satisfying f(M,y,,z) 0. We use this fact to compute f(x,y,,z). More concretely, we determine the coefficients of f(x,y,,z) little by little with basic matrix operations, which makes the algorithm quite efficient. Numerical experiments are given to compare the algorithm with conventional ones.

In this paper, we focus on the evaluation of the Erlang capacity for multimedia DS-CDMA systems supporting the multi-class services with different transmission rates, bit error rates, traffic activity factors in the reverse link. The number of concurrent users of the corresponding service group is modeled as a K-dimension Markov chain. Then, the Erlang capacity for the multimedia system can be found based on a K-dimension M/M/m loss system. For an IS-95 type DS-CDMA system, supporting voice/data services, the capacity bounds are depicted in conjunction with the 2-dimensional Markov chain. Furthermore, it is observed that the Erlang capacity with respect to the each service group should be balanced to enhance the total system Erlang capacity. Finally, the channel reservation scheme is considered to increase the total system Erlang capacity.

Cerebellar Model Articulation Controller (CMAC) has been proposed as one of artificial neural networks. This paper describes a design scheme of intelligent control system consists of some CMACs. Each of CMACs is trained for the specified reference signal. A new CMAC is generated for unspecified reference signals, and the CMAC whose reference signal is nearest for the new reference signal, is eliminated. Therefore, since the reference signals are removed from the input signals of the CMAC, the proposed intelligent controller can be designed with fairly small memories.

This letter proposes improvement to the previously presented watermarking method which spreads an ID pattern with a random sequence and embeds it throughout the spatial domain of an image. The proposed method can extract embedded watermarks without an original image even from images converted by brightness/contrast conversion, edge-enhancement, posterization and JPEG compression.