In location problems, the outtransmission and intransmission numbers are important indices to evaluate a directed network. We formulate and consider a new problem of fault diagnosis in a system modeled by a directed network in which to each edge a positive real number called the length of edge is assigned and to each vertex a positive real number called the weight of vertex is assigned. By a fault in a directed network, we mean any increase in the length of an edge with respect to its nominal length. A theory and an algorithm for detecting a fault edge in a directed network in which the above indices, i.e. outtransmission and/or intransmission numbers, are measurable, are presented.

This paper shows that the strong Minkowski decomposition problem is NP-complete. Given two convex polygons α and β, the Minkowski sum α+β is a convex polygon defined by {(ax+bx, ay+by|(ax+ay)α, (bxby)β}. The Minkowski decomposition problem is for a given convex polygon γ to find two non-trivial convex polygons α and β whose Minkowski sum is γ. Silverman and Stein gave a linear-time algorithm for this problem. The strong Minkowski decomposition problem is to decompose a given convex polygon into two convex polygons in such a way that any pair of edges of two polygons are not in parallel. It is well known that the Minkowski sum of two convex polygons can be computed in linear time with respect to the number of edges involved. The NP-completeness result of the strong Minkowski decomposition problem shows interesting contrast to the following two results: One is that its inverse operation, the Minkowski sum operation, can be computed in linear-time; Another result, recently obtained by Mount and Silverman, is that the strong Minkowski operation for a convex polyhedron in R3 is also linear-time computable.

Consider a connected network N. With each edge of N we associate a nonnegative real number called the length of the edge. Let N be a network obtained from N by adding new edges and/or by decreasing the lengths of some edges. For a generalized transmission number cf(N, v) defined on vertex v in N, we call Δc(v)=cf(N, v)-cf(N ,v) the Sabidussi difference of vertex v. In this note, we present a new theorem and its corollaries on the Sabidussi difference.

In this paper we present polynomial time algorithms for the following three problems on a Hamilton graph with a prescribed Hamilton circuit: (1) Given a Hamilton graph G with a prescribed Hamilton circuit, find a maximal planar Hamilton subgraph of G, (2) Given a Hamilton graph G and a planar Hamilton subgraph H of G, find a maximal planar Hamilton subgraph of G that contains H, and (3) Given an edge-weighted Hamilton graph G=(V, E), find a planar Hamilton subgraph G=(V, E) of G such that the addition of an edge e E-Edestroys the planarity, unless we delete an edge from Ehaving no less weight than e. The time complexities of the algorithms are O(n+m), O(m3/2) and O(m5/3), respectively, where n(resp., m) is the number of vertices (resp., edges) of the Hamilton graph. These algorithms are applicable to the Topological Via Minimization problem.

We introduce the distance between two edges in a graph (nondirected graph) as the minimum number of edges in a tieset with the two edges. Using the distance between edges we define the eccentricity ετ (ej) of an edge ej. A finite nonempty set J of positive integers (no repetitions) is an eccentric set if there exists a graph G with edge set E such that ετ (ej) J for all ei E and each positive integer in J is ετ (ej) for some ej E. In this paper, we give necessary and sufficient conditions for a set J to be eccentric.

Most of the late generation nonvolatile memories with moderate access speed are designed with divided memory matrix NOR type cell structure because word and bit-lines carry a uniform array of parasitic capacitance which delays the signal propagation and causes the slow down of data access time. Even though divided memory matrix has short matrix drive a chip size penalty is large. Data read function of conventional ROM devices is performed by applying VSS voltage at source of each memory cell MOS transistor. Selected memory cells are applied with a predetermined high-detecting bias (HDB) at the drain through selected bit-line. The current detector connected to these bit-lines detectes the level of current to maintain the bias against cell current. New low detecting bias (LDB) technology improves the data access time from wide memory cell matrix area that must be driven by long-word lines (row) and long bit-lines (column). By implementing the (LDB) ROM architecture, voltage transient time of a word line, transition period of voltage against parasitic capacitance and detection period of bit-line voltage deviation can be improved significantly.

In this paper, a network of communicating logic programs is proposed as a model for concurrent programming based on logic programs with explicit channels of communications. On the assumption that the denotations of channels are defined by using a sequence domain, semantics for unbounded nondeterminism caused by logic programs is dealt with and the whole network is defined as an extension of Kahn's pure dataflow. A denotational semantics for the whole network is defined by a recursive relation set as to the histories of channels. The method to investigate extensionality of input-output histories on the node in nondeterministic dataflow is not applicable to the proposed network, because the node is a logic program. Fairness is required for unbounded nondeterminism to describe the behaviour of the whole network. And in this paper the corresponding semantics of the network is shown. We have a method of defining a continuous function which is associated with the network, based on histories of channels. The least fixpoint of the function is regarded as a denotational semantics for the whole network, to reflect its fair behaviours.

Two approaches are known for enhancing the fault tolerance of systolic arrays through reconfiguration. They are different in the bypassing function. One leads to an easier reconfiguration procedure, whereas the other provides better utilization of nonfaulty cells. It seems that both approaches may have the same probability of successful reconfiguration for practical failure rates of cells but not for all other failure rates. In this paper, we investigate this supposition, and conclude that the two approaches perform equally well for all practical cell failure rates and array sizes.

In this paper, we will propose a modified Euclidean algorithm which can be obtained by examining thoroughly the equivalence between conventional Euclidean algorithm and Berlekamp-Massey algorithm. Furthermore, we will show the design method for BCH decoders and Inverters based on the modified Euclidean algorithm in which the minimum number register realization is given.

Leakage current in SCC DRAM was reduced by optimizing implant conditions to form channel stopper, node connection and Hi-C boron. To reduce leakage current, the implantation doses should be reduced to reduce implant induced damages. These implant dose reductions are compromised to the necessities of high p type concentration to prevent punch-throughs at several parts of the cell. Near the deep trench bottom, damaged region due to Hi-C boron implant is separated from the bottom edge of the n+ storage node to suppress the gate controlled leakage current. By the improvements, the retention time of the 16 M SCC DRAM becomes over 30 sec at room temperature. It is also shown that folded bit line structure could be adopted easily for SCC.

We present an algorithm for finding a maximum weight independent set of a circle graph. For a cicle graph of a set of n chords with N endpoints, the algorithm finds a maximum weight independent set in O(nN) time and O(n) space.

Enhancing the ISDN (Integrated Services Digital Network) capability to cover broadband capacity will change the telecommunication world greatly. This paper discusses the way where telecommunication networks should be evolved, the main features of the ATM (Asynchronous Transfer Mode) based B-ISDN, and its basic structure principles with the close relationship to customers' demands. ATM will play a key role in technology toward the B-ISDN. This paper proposes a concept of "ATMization" as the next technical revolution step coming after "digitalization". Firstly, various customers' views are summarized as four evaluation factors, and the scheme of the B-ISDN to reflect these customers demands are discussed. Then, by clearing the role of B-ISDN as the transport infrastructure, it is proposed that service control and OAM information be transferred by the ATM infrastructure. Based on these considerations, basic structure of B-ISDN and four scenario elements toward the ATMized B-ISDN era are further proposed.

We report the results of experiments on a Josephson RAM having an access time of 590 ps and a power dissipation of 19 mW. To design such high-speed memory, we developed new gates and circuits and used high-speed techniques. This paper details the design of the 4K bit Josephson RAM.

A new algebraic solution is developed for nonlinear integral/ differential equations including power-law or product-type nonlinearities. The new method performs the computation via PL transform using multiplication operator with the aid of integral operator through iterative calculations. This method is capable of solving integral or integro-differential equations without converting the equation into a equivalent differential equation. The method is also capable of solving higher-order differential equations without converting the equation into a set of simultaneous first order differential equations. Examples show that a good accuracy was obtained using a limited length PL transform through a small number of iterations.

In this paper, we consider an automatic warehouse, in which rc-k palettes are arranged two-dimensionally on a grid with r rows c columns. The palettes in the warehouse can slide independently and simultaneously with the use of k spaces, unless they come into collision. Then, we show the minimum number of sliding operations required to move a specified palette to a specified position, where one sliding operation is a set of slides of palettes which are executed simultaneously in a unit time withouto any collision.

If π is a monotone property on graphs (that is, π is attainable by adding edges to a given graph), then the graph augmentation problem with respect to π is defined by: "Given a graph G=(V, E) and nonnegative weights w(u, v) for all pairs {u, v} VV (uv), find an edge set Eof minimum total weight such that the graph G=(V, EE) satisfies π, where we assume that w(u, v)=0 for every edge (u, v) E". The subject of the paper is to give an overview of the graph augmentation problems where π is concerned with vertex-or edge-connectivity of graphs. Also presented are basic ideas used in solving this problem.

ATM's bandwidth flexibility and high switching speed advantages have made it the preeminent solution to the B-ISDN. However, networks based on ATM suffer from phenomena not encountered in the STM network, e.g., cell loss, and cell jitter. For ATM to support varied media, problems arising from these phenomena must be resolved. This paper discusses techniques which enable ATM to support CBR, VBR voice, VBR video, and connectionless services. We determine the problems to be resolved for each service and discuss solutions. We focus on dejittering and clock recovery for CBR service, on talk-spurt synchronization for VBR voice, and on video frame synchronization and lost-cell compensation for VBR video service. We show experimental results for a prototype HDTV codec and terminal adapter. For connectionless service, we show that connectionless service should be supplied by the B-ISDN itself using message handlers which support message routing and addressing, i.e., connectionless service functions (CLSF), as described by the CCITT. We propose a network topology of message handlers, which reduces the routing database and avoids transit message handler overload. We show an example of system configuration for connectionless service.

This paper reviews various switch architectures for Asynchronous Transfer Mode, which have been proposed and developed so far in Japan. The switch fabrics can be classified, owing to the arrangement of switch matrices and buffer memories, into four categories, input buffer switch, output buffer switch, shared buffer switch and crosspoint buffer switch. Those switches have their own advantages and disadvantages, which require additional effort to implement the switches for the practical network. This paper introduces examples of each category switch fabric and additional technical modifications to make it practical. Other general issues to construct ATM switch fabrics, such as non-blocking characteristics and path assignment within a multi-stage switch network, are also addressed. Furthermore, future directions in the ATM switch fabric is discussed.