Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.

Alternative wiring techniques have been shown to be very useful for many EDA problems. The currently used rewiring techniques are mainly ATPG based. In this paper, we study the approach of applying purely graph-based local pattern search methods in locating alternative wires. The method searches minimal graph patterns containing alternative wires that limited to 2 edges distant from the target wire. The experimental result shows that this scheme is very fast and has the advantage of searching both the nearby forward and backward alternative wires easily. The overall number of alternative wires searched is quite comparable (104%), compared to the forward search only RAMBO version, and the CPU time is 200 times faster. We also illustrate its usage, among many others, by a simple coupling with the SIS algebraic operations and let this rewiring tool serve as a netlist-perturbing engine for logic minimization. The coupling scheme shows a further reduction of 8.5% in area compared to applying algebraic script alone, with a nearly negligible CPU overhead spent in rewiring.

A management of WWW server is still relying on the expertise and heuristic of administrators, because the comprehensive understandings of server behavior are missing. The administrators should maintain the WWW server with good states that they should investigate the WWW server in real time. Therefore, it is exactly desirable to provide a measurement application that enables the WWW server administrators to monitor WWW servers in the actual operational environment. We developed a measurement application called ENMA (Enhanced Network Measurement Agent) which is specially designed for WWW server state analysis. Furthermore, we applied this application to the large scale WWW server operation to show its implementation and advantages. In this paper, we analyze the WWW server states based on precise monitoring of performance indices of WWW system to help the server management.

Leaky waves have been known for many years in the context of leaky-wave antennas, but it is only within the past dozen years or so that it was realized that the dominant mode on printed-circuit transmission lines used in microwave and millimeter-wave integrated circuits can also leak. Such leakage is extremely important because it may cause power loss, cross talk between neighboring parts of the circuit, and various undesired package effects. These effects can ruin the performance of the circuit, so we must know when leakage can occur and how to avoid it. In most cases, these transmission lines leak only at high frequencies, but some lines leak at all frequencies. However, those lines can be modified to avoid the leakage. This paper explains why and when leakage occurs, and shows how the dominant mode behaves on different lines. The paper also examines certain less well known but important features involving unexpected new physical effects. These include an additional dominant mode on microstrip line that is leaky at higher frequencies, and a simultaneous propagation effect, which is rather general and which occurs when the line's relative cross-sectional dimensions are changed. The final section of the paper is concerned with three important recent developments: (a) the new effects that arise when the frequency is raised still higher and leakage occurs into an additional surface wave, (b) a basic and unexpected discovery relating to improper real modes, which are nonphysical but which can strongly influence the total physical field under the right circumstances, and (c) the important practical issue of how leakage behavior is modified when the circuit is placed into a package.

We study the evolution and the dominance of the service based functions and their distinguishing features. As the service industry matures, its functions bear many similarities with the software development processes, such as intense man-machine interaction, knowledge intensive activities, flexibility in the organization, control and execution of tasks. In this paper we discuss wide range of interconnected topics, emphasizing the multi-faceted nature of service functions. These include the evolution of service industry and their products, the consumerization of high tech products based on their large-scale adoption and the consequent creation of implicit requirements; the technology transfer processes; the error proneness due to intense and prolonged interaction with computers and some methods of mitigating error incidence. We argue that by proper 'humanization and personalization' of interactive systems and by the use of teams of computer supported professionals, we can prevent such errors. We discuss some useful team types, models of their behavior and their control aspects. As the cost of communications shrinks like due to the Internet, we conclude that a fully decentralized system control provides a flat, flexible, and fair and friction-free organization for large team based service systems.

This paper describes the Profit-Sharing, a reinforcement learning approach which can be used to design a coordination strategy in a multi-agent system, and demonstrates its effectiveness empirically within a coil-yard of steel manufacture. This domain consists of multiple cranes which are operated asynchronously but need coordination to adjust their initial plans of task execution to avoid the collisions, which would be caused by resource limitation. This problem is beyond the classical expert's hand-coding methods as well as the mathematical analysis, because of scattered information, stochastically generated tasks, and moreover, the difficulties to transact tasks on schedule. In recent few years, many applications of reinforcement learning algorithms based on Dynamic Programming (DP), such as Q-learning, Temporal Difference method, are introduced. They promise optimal performance of the agent in the Markov decision processes (MDPs), but in the non-MDPs, such as multi-agent domain, there is no guarantee for the convergence of agent's policy. On the other hand, Profit-Sharing is contrastive with DP-based ones, could guarantee the convergence to the rational policy, which means that agent could reach one of the desirable status, even in non-MDPs, where agents learn concurrently and competitively. Therefore, we embedded Profit-Sharing into the operator of crane to acquire cooperative rules in such a dynamic domain, and introduce its applicability to the realistic world by means of comparing with RAP (Reactive Action Planner) model, encoded by expert's knowledge.

The reconfiguration latency defined as the time taken for reconfiguring a system upon failure detection or mode change. We evaluate it quantitatively for backup sparing, which is one of the most popular reconfiguration methods, by investigating the effects of key parameters.

Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

In this paper, we propose a method for detecting conserved domains from a set of amino acid sequences that belong to a protein family. This method detects the domains as follows: first, generate fixed-length subsequences from the sequences; second, construct a weighted graph that connects any two of the subsequences (vertices) having higher similarity than a pre-defined threshold; third, search for the maximum-density subgraph for each connected component of the graph; finally, explore conserved domains in the sequences by combining the results of the previous step. From the performance results obtained by applying the method to several protein families that have complex conserved domains, we found that our method was able to detect those domains even though some domains were weakly conserved.

Although there are many projects focusing on multiagent systems, there are only a few focusing on systematic design of large scale multiagent system. In this paper we formalize the knowledge representation and sharing of agents, using symbol structures, define agencies as organizations (i. e. , a coalition of agents), propose a formalism to represent organizational Intelligence, devise a basic configuration for generalized agents (AG), and use them in a large scale multiagent system design. Private knowledge of an AG agent is represented by a symbol structure (SS) and AG agents can share their knowledge using combination, specialization and generalization methods that operate on the SS. Opposite to the other works, organizational knowledge, is defined as a property of at least a pair of AG agents.

In a software maintenance phase, since quality assurance engineers frequently only change source codes, the consistency between the source codes and their specification documents cannot be kept. In this paper we propose a supporting technique for changing specification documents automatically so that the specifications can be consistent with the source codes. In our technique, we represent a program with multiple graphs and we consider the changes on programs as the modification of the graphs. The modification of the graphs is formalized with a sequence of the operation on the graphs. We design the rules of how to relate the operations on program graphs to the operations on graphs that represent specification documents. By applying these rules, we can detect what modification and which parts of the specification document should be made to maintain the consistency between the specification and the program, when the program is modified.

The construction of photo-realistic 3D scenes from video data is an active and competitive area of research in the fields of computer vision, image processing and computer graphics. In this paper we address our recent work in this area. Unlike most methods of 3D scene construction, we consider the generation of virtual environments from video sequence with a video-cam's forward motion. Each frame is decomposed into sub-images, which are registered correspondingly using the Levenberg-Marquardt iterative algorithm to estimate motion parameters. The registered sub-images are correspondingly pasted together to form a pseudo-3D space. By controlling the position and direction, the virtual camera can walk through this virtual space to generate novel 2D views to acquire an immersive impression. Even if the virtual camera goes deep into this virtual environment, it can still obtain a novel view while maintaining relatively high resolution.

To bridge a wide gap between the end users and the requirements engineers, we propose a business flow diagram for acquiring users' requirements of the object oriented software development in the business application domain. Each field of this diagram shows either a role or a responsibility of a particular person or an organization. This paper proposes a development method that the engineers acquire the requirements by using our diagrams. We have implemented a supporting tool based on this study for collaborating the requirements engineers with their users. At first, the end users of an information system to be developed draw diagrams representing the flows of information and physical objects in their work from their own points of view. Sometimes the engineers write them with the users. If all users submit their diagrams, then our tool collects them and constructs a total diagram. The requirements engineers analyze the total diagram for improving the business flow. After the engineers complete this diagram, our tool can automatically transform it into an initial version of the class diagram. We show the effectiveness of our approach with some experiments. Comparing the related works, we discuss some issues of the practical aspects of this proposal.

This paper proposes an intelligent image interpolation method based on Cubic Hermite procedure for improving digital images. Image interpolation has been used to create high-resolution effects in digitized image data, providing sharpness in high frequency image data and smoothness in low frequency image data. Most interpolation techniques proposed in the past are centered on determining pixel values using the relationship between neighboring points. As one of the more prevalent interpolation techniques, Cubic Hermite procedure attains the interpolation with a 3rd order polynomial fit using derivatives of points and adaptive smoothness parameters. Cubic Hermite features many forms of a curved shape, which effectively reduce the problems inherent in interpolations. This paper focuses on a method that intelligently determines the derivatives and adaptive smoothness parameters to effectively contain the interpolation error, achieving significantly improved images. Derivatives are determined by taking a weighted sum of the neighboring points whose weighting function decreases as the intensity difference of neighboring points increases. Smoothness parameter is obtained by training an exemplar image to fit into the Cubic Hermite function such that the interpolation error is minimized at each interpolating point. The simulations indicate that the proposed method achieves improved image results over that of conventional methods in terms of error and image quality performance.

This paper discusses the characteristics of human design knowledge. By studying a number of actual human made designs of excellent designers, the most frequent basic mental operations of a typical human designer have been found. They are: a design rule for hierarchical detailing reported previously, a micro design rule for generating a hierarchical expansion, dictionary operations to build a micro design rule and dictionaries. This study assumes a multiplicity of knowledge based on Zipf's theory, "the principle of least effort. " Zipf's principle may be proved and it becomes possible to understand the fundamental nature of human design.

Distributed shared memory (DSM) systems on top of network of workstations are especially vulnerable to the impact of false sharing because of their higher memory transaction overheads and thus higher false sharing penalties. In this paper we develop a dynamic-granularity shared memory management scheme that eliminates false sharing without sacrificing the transparency to conventional shared-memory applications. Our approach utilizes a special threaded splay tree (TST) for shared memory information management, and a dynamic token-based path-compression synchronization algorithm for data transferring. The combination of the TST and path compression is quite efficient; asymptotically, in an n-processor system with m shared memory segments, synchronizing at most s segments takes O(s log m log n) amortized computation steps and generates O(s log n) communication messages, respectively. Based on the proposed scheme we constructed an experimental DSM prototype which consists of several Ethernet-connected Pentium-based computers running Linux. Preliminary benchmark results on our prototype indicate that our scheme is quite efficient, significantly outperforming traditional schemes and scaling up well.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.

The wavelength demultiplexer, using cascaded optical fiber gratings and circulators, was proposed and developed for application to optically amplified wavelength-division multiplexing (WDM) submarine cable systems with 100 GHz channel spacing. Our proposed demultiplexer cannot only achieve high wavelength selectivity, small excess loss and effective allocation of dispersion compensation fibers for each channel, but also be upgraded without affecting other existing channels. By using this demultiplexer, it has been successfully confirmed that 8 WDM channels were demultiplexed even after 6,000 km transmission including separate compensation of accumulated chromatic dispersion in each channel.

Since river levee collapse causes great damage, it is socially very important to prevent such disasters by using a monitoring system which can detect changes in the state of a river levee. To investigate the possibility of detecting the collapse of a levee slope at an early stage, we performed an experiment in which we used artificial rainfall and penetration to collapse a full-scale levee model, and measured the change in the levee state using a detection system during collapse. The system consists of sensor plates, a distributed fiber optic strain sensor, and a personal computer. With this system, the stretching produced in the sensor plates by the force resulting from the movement of the soil on the levee slope face is detected as strain by a sensing optical fiber fixed to the plates. Since the distributed fiber optic strain sensor can measure strain continuously and for a long distance along a fiber, it is suitable for monitoring civil structures such as river levees. The experiment confirmed that a change in a levee can be clearly detected when the slope face collapse progresses near the place where the sensor plates are buried. The results suggest the feasibility of being able to foresee the collapse of a levee slope.

A correlation-based technique for measuring Brillouin gain spectrum distribution along an optical fiber is proposed, which employs frequency-modulated pump and probe lightwaves. The spatial-resolution of about 40 cm is demonstrated, which cannot be realized by the conventional pulse-based technique.