We present a restructuring method to apply a degradation approach to mesh-connected processor arrays with spare processing elements on the orthogonal sides of the arrays. An array with faulty processing elements is restructured by shifting healthy processing elements toward faulty processing elements using single track switches. First, an algorithm which satisfies the necessary and sufficient condition (called a restructurable condition) that an array is restructured so that its logical size is kept is briefly explained. Next, a method that if the array does not satisfy the restructurable condition, its rows and/or columns are functionally deleted so that the subarray with the remaining rows and columns satisfies the restructurable condition is presented. Finally, the simulation results are shown.

An array with spares on four sides and the restructuring algorithm for it were proposed in [1]. However, the restructuring algorithm described in [1] is too complicated to be realized in hardware. Here, we propose a method to improve such the situation. First, the array is considered to be an (N +2) (N +2) array if four PEs are added to the four corners of the array and the spares are included. The (N+2) (N+2) array is divided into four subarrays, each of which is of size (N=2 + 1)(N=2 + 1), and the orthogonal side rotation introduced here is individually applied to each subarray. The reliabilities are given by computer simulation. They fairly increase, comparing with those in [1].

We present a built-in self-restructuring system for a mesh-connected processor array where faulty processing elements are compensated for by spare processing elements located on a diagonal. First, an algorithm for restructuring the array with faulty processing elements is presented. The reliability of the system is analyzed by simulation. It is compared with that of an array with spare processing elements on a line at the edge of the array which has the same number of spare processing elements as that in the proposed array. It is shown that the former is fairly higher than the latter. Next, a logical circuit realizing the algorithm is presented. The circuit controls interconnection of processing elements and is so simple that its hardware overhead is small. The proposed system is effective for the case where each processing element is fairly reliable and the small number of spares will be enough for retaining the reliability of an array so high under small hardware overhead. It is also effective in enhancing especially the run-time reliability of a processor array.

We present a self-repairing circuit for a mesh-connected processor array with faulty processing elements which are directly replaced by spare processing elements on two orthogonal lines at the edges of the array. First, the spare assignment problem is formalized as a matching problem in graph theory. Using the result, we present an algorithm for reconstructing the array in a convenient form for finding the matching by a logical circuit. Second, the logical circuit which exactly realizes the algorithm is given. The circuit can be embedded in a target processor array to reconstruct very quickly the array with faulty processing elements without the aid of a host computer. This implies that the proposed system is effective in enhancing especially the run-time reliability of a processor array.

We propose an efficient method for making multilayered neural networks(MLN) fault-tolerant to all multiple weight faults in an interval by injecting intentionally two extreme values in the interval in a learning phase. The degree of fault-tolerance to a multiple weight fault is measured by the number of essential multiple links. First, we analytically discuss how to choose effectively the multiple links to be injected, and present a learning algorithm for making MLNs fault tolerant to all multiple (i.e., simultaneous) faults in the interval defined by two multi-dimensional extreme points. Then it is shown that after the learning algorithm successfully finishes, MLNs become fault tolerant to all multiple faults in the interval. The time in a weight modification cycle is almost linear for the fault multiplicity. The simulation results show that the computing time drastically reduces as the multiplicity increases.

For a redundant (array) system, he (or she) who considers that the total system reliability might be worse than a nonredundant system because of additional circuit faults might naturally say, "Is the redundancy really useful?". The main purpose of the paper is to answer the question for redundant array systems using E-1 1/2 track switches (Tadayoshi Horita and Itsuo Takanami, 2000) and a reconfiguration method. The answer is "the redundancy using these methods is useful!". Furthermore, the condition that the assumption that additional circuits such as tracks, switches, etc. are fault-free becomes valid is given.

Many studies of methods for making multilayer neural nets (MNN) fault-tolerant by injecting intentionally the snapping of a link or a noise into links in the learning process have considered fault-tolerance to link snapping. We consider fault-tolerance to the weight fault, which includes link snapping as a special case. We take a pattern recognition problem as an example. To make an MNN fault-tolerant to any single or double weight faults in a certain interval or range, we inject intentionally two extreme points of a single or double fault-values in an interval or a range during learning. By simulation, we investigate how much MNN becomes fault-tolerant to the weight faults depending on the injected ones. The degree of fault-tolerance for a n-multiple weight fault is estimated by the number of essential multiple links. An interesting result that if only two faults of the extreme points in the interval are injected, the number of the essential links becomes zero for single faults of all the weights in the interval is obtained. This means that MNN becomes fault-tolerant to any single weight faults in the interval. Expecting that the similar result for double faults will be obtained, we inject two extreme points in two-dimensional range. As expected, the number of 2-multiple essential links has become zero in the range. This means that MNN becomes fault-tolerant to any double weight faults in the range. Finally, we analyse the internal structure of MNN by the distribution of covariance between any two inputs of a neuron in the output layer.

A mesh-connected processor array consists of many similar processing elements (PEs) which can be executed in both parallel and pipeline processing. For the implementation of an array of large numbers of processors, some fault-tolerant issues are necessary to enhance the (fabrication-time) yield and the (run-time) reliability. In this paper, we propose a fault-tolerant reconfigurable processor array using single-track switches like Kung et al.'s model. The reconfiguration process in our model is executed based on the concept of the "compensation path" like Kung et al.'s method, too. In our model, spare PEs are not necessarily put around the array, but are more flexibly put in the array by changing connections between spare PEs and nonspare PEs while retaining the connections among nonspare PEs in the same manner in Kung et al.'s model. The proposed model has such a desirable property that physical distances between logically adjacent PEs in the reconfigured array are within a constant, that is, independent of sizes of arrays. We show that the hardware overhead of the proposed model is a little greater than that of Kung et al.'s model, while the yield of the proposed model is much better than that of Kung et al.'s model.

To make a neural network fault-tolerant, Tan et al. proposed a learning algorithm which injects intentionally the snapping of a wire one by one into a network (1992, 1992, 1993). This paper proposes a learning algorithm that injects intentionally stuck-at faults to neurons. Then by computer simulations, we investigate the recognition rate in terms of the number of snapping faults and reliabilities of lines and the learning cycle. The results show that our method is more efficient and useful than the method of Tan et al. Furthermore, we investigate the internal structure in terms of ditribution of correlations between input values of a output neuron for the respective learning methods and show that there is a significant difference of the distributions among the methods.

Recently, related to the open problem of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, the inkdot Turing machine was introduced. An inkdot machine is a conventional Turing machine capable of dropping an inkdot on a given input tape for a landmark, but not to pick it up nor further erase it. In this paper, we introduce a finite state version of the inkdot machine as a weak recognizer of the properties of digital pictures, rather than a Turing machine supplied with a one-dimensional working tape. We first investigate the sufficient spaces of three-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensional inkdot automaton, i.e. the hierarchy based on the number of inkdots and the relationship of two-dimensional inkdot automata to other conventional two-dimensional automata. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines.

This paper introduces a cooperating system of three-way, two-dimensional finite automata (CS-TR2-FA) which is a restricted version of a cooperating system of four- way, two-dimensional finite automata (CS-2-FA), and mainly investigates several fundamental properties of this system as a two-dimensional language acceptor whose input tapes are restricted to square ones. We show that (1) CS-TR2-FA’s are equivalent in accepting power to three-way, two-dimensional simple multihead finite automata, (2) CS-2-FA’s are more powerful than CS-TR2-FA’s, (3) £[CS-TR2-DFA(k)S] ⊊ £[CS-TR2-NFA(k)S], (4) ⋃1≤k<∞ £[CS-TR2-DFA(k)S] ⊊ ⋃1≤k<∞ £[CS-TR2-NFA(k)S], and (5) £[CS-TR2-DFA(k)S] (£[CS-TR2-NFA(k)S]) ⊊ £[CS-TR2-DFA(k+1)S] (£[CS-TR2-NFA(k+1)S]), where £[CS-TR2-DFA(k)S] (£[CS-TR2-NFA(k)S]) denotes the class of sets of square input tapes accepted by CS-TR2-FA’s which consist of k deterministic (non-deterministic) finite automata.

This paper first shows that REC, the family of recognizable picture languages in Giammarresi and Restivo,3 is equal to the family of picture languages accepted by two-dimensional on-line tessellation acceptors in Inoue and Nakamura.5 By using this result, we then solve open problems in Giammarresi and Restivo,3 and show that (i) REC is not closed under complementation, and (ii) REC properly contains the family of picture languages accepted by two-dimensional nondeterministic finite automata even over a one letter alphabet.

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k+1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k≥1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is nk+1, where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.

This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that Ω ( diameter × log diameter ) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim n → ∞ L (n)/ loglog n > 1 and L (n) ≤ log n, and L′ (n) is a function satisfying L′ (n) =o (L(n)), then there exists a set accepted by some strongly L (n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L′ (n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S (n) space-bounded 2-ATMs with loglog n ≤ S (n) ≤ log n.

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM1 (2-NM1), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM1s (2-NM1s) is n log n (n2), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM1s (2-NM1s) is 2O(n log n) (2 O(n2)), where n is the number of columns of rectangular input tapes.

This paper introduces a two-dimensional alternating Turing machine (2-ATM) which is an extension of an alternating Turing machine to two-dimensions. This paper also introduces a three-way two-dimensional alternating Turing machine (TR2-ATM) which is an alternating version of a three-way two-dimensional Turing machine. We first investigate a relationship between the accepting powers of space-bounded 2-ATM's (or TR2-ATM's) and ordinary space-bounded two-dimensional Turing machines (or three-way two-dimensional Turing machines). We then introduce a simple, natural complexity measure for 2-ATM's (or TR2-ATM's), called “leaf-size”, and provides a spectrum of complexity classes based on leaf-size bounded computations. We finally investigate the recognizability of connected patterns by 2-ATM's (or TR2-ATM's).

A tour in a sequential machine is a shortest input sequence taking the machine from some initial state, through all of its remaining states and back again into its initial state. A. K. Dewdney and A. L. Szilard [2] found the best upper bound for tour length for two classes of machines: the class of n-state sequential machines with unrestricted input alphabet and the class of n-state sequential machines with a two-letter input alphabet. We define a strong circulation on a strong digraph D whose volume is equal to the tour length of D. Characterizing the volume of strong circulation, we derive the best upper bound for tour length for n-state sequential machines with an r-letter input alphabet. Putting $r = 2$ or $r = \infty $, we have the same results as those obtained by A. K. Dewdney and A. L. Szilard.