We consider a class of unknown scenes Sk(n) with rectangular obstacles aligned with the axes such that Euclidean distance between the start point and the target is n, and any side length of each obstacle is at most k. We propose a strategy called the adaptive-bias heuristic for navigating a robot in such a scene, and analyze its efficiency. We show that a ratio of the total distance walked by a robot using the strategy to the shortest path distance between the start point and the target is at most 1+(3/5) k, if k=o(n) and if the start point and the target are at the same horizontal level. This ratio is better than a ratio obtained by any strategy previously known in the class of scenes, Sk(n), such that k=o(n).

The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows： Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.

This paper advocates the use of linear objective function in analytic analog placement. The role of linear and quadratic objctive functions in the behavior and results of an analog placement algorithm based on the force directed method is discussed. Experimental results for a MCNC benchmark circuit and another one from text books are shown to demonstrate the effect of a linear and a quadratic objective function on the analog constraint satisfaction and CPU time. By introducing linear objective function to the algorithm, we obtain better placements in terms of analog constraint satisfaction and computation cost than in case of conventional quadratic objective function.

This paper studies the problem of embedding a graph into a book with nodes on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. Atneosen as well as Bernhart and Kainen has shown that every graph can be embedded into a 3-page book when each edge can be embedded in more than one page. The time complexity of Bernhart and Kainen's method is Ω(ν(G)), where ν(G) is the crossing number of a graph G. A new 0(mn) algorithm is derived in this paper for embedding a graph G=(V, E), where m=│E│ and n= │V│ . The number of points at which edges cross over the spine in embedding a complete graph into a 3-page book is also investigated.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

This paper presents a linear time algorithm for testing whether or not there is a path ,vm> of an undiercted tree T (|V(T)|n) that coincides with a string ss1sm (i.e., label(v1)label(vm)s1sm). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

As RAMs become dense, their reliability reduces because of complex interactions between memory cells and soft errors due to alpha particle radiations. In order to rectify this problem, RAM manufacturers have started incorporating on-chip (built-in) ECC. In order to minimize the area overhead of on-chip ECC, the same technology is used for implementing the check bits and the information bits. Thus the check bits are exposed to the same failure modes as the information bits. Furthermore, faults in the check bits will manifest as uncorrectable multiple errors when a soft error occurs. Therefore it is important to test the check bits for all failure modes expected of other cells. In this paper, we formulate the problem of testing RAMs with on-chip ECC capability. We than derive necessary and sufficient conditions for testing the check bits for arbitrary and adjacent neighborhood pattern sensitive faults. We also provide an efficient solution to test a memory array of N bits (including check bits) for 5-cell neighborhood pattern sensitive faults in O (N) reads and writes, with the check bits also tested for the same fault classes as the information bits.

An adaptive multichannel IIR lattice predictor for k-step ahead prediction is constructed and the effectiveness of the proposed predictor is evaluated using digital simulations.

This paper presents efficient algorithms for finding the largest tree S such that there are vertex disjoint subtrees S1, , S (k1) of T each of which is isomorphic to S and every leaf of T is a leaf of some Si. The algorithms are useful for learning a macro table.

The performance of analog circuits is strongly influenced by their layout. Performance specifications are usually translated into physical constraints such as symmetry, common orientation, and distance constraints among certain components. Automatic digital layout tools can be adopted and modified to deal with the imposed performance constraints on the analog layout. The selection and modifications of algorithms to handle the analog constraints became the area of research in analog layout systems. The existing systems are characterized by the use of stochastic optimization techniques based placement, grid based or channel routers, and lack of compaction. In this paper, algorithms for analog circuit placement, routing, and compaction are presented. The proposed algorithms consider the analog oriented constraints, which are important from an analog layout point of view, and reduce the computation cost. The placement algorithm is based on a force directed method and consists of two main phases, each of which includes a tuning procedure. In the first phase, we solve a set of simultaneous linear equations, based upon the attractive forces. These attractive forces represent the interconnection topology of given blocks and some specified constraints. Symmetry constraint is considered throughout the tuning procedure. In the second phase, block overlap resulting from the first phase is resolved iteratively, where each iteration is followed by the symmetry tuning procedure. Routing is performed using a line expansion based gridless router. Routing constraints are taken into account and several routing priorities are imposed on the nets. The compactor part employs a constraint graph based algorithm while considering the analog symmetry constraints. The algorithms are implemented and integrated within an analog layout design system. An experimental result for an OP AMP provided by MCNC benchmark is shown to demonstrate the performance of the algorithms.

A genetic method to generate a neural network which has both structure and connection weights adequate for a given task is proposed. A neural network having arbitrary connections is regarded as a virtual living thing which has genes representing its connections among neural units. Effectiveness of the network is estimated from its time sequential input and output signals. Excellent individuals, namely appropriate neural networks, are generated through generation iterations. The basic principle of the method and its applications are described. As an example of evolution from randomly generated networks to feedforward networks, an XOR problem is dealt with, and an action control problem is used for making networks containing feedback and mutual connections. The proposed method is available for designing a neural network whose adequate structure is unknown.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

An optimal algorithm for decomposing a special type of the Hasse diagram into a minimum set of disjoint paths is described. It is useful for testing the consistency of functional dependencies.

In this paper we present and analyze multi-level quorum schemes for maintaining the consistency of replicated data in the presence of concurrency and failures in a large distributed environment. The multi-level quorum method operates on a logical hierarchy of the nodes in the network and applies well known flat voting algorithms for replicated data concurrency control in a layered fashion. We show how the number of hierarchy levels, the number of logical entities per level and the voting algorithms used on each level affect the costs and the degree of availability associated with a wide range of multi-level quorum schemes. The results of the analysis are used to provide guidelines for designing the most suitable multi-level quorum strategy for a given application scenario. Comparative performance measurements in a simulated network are presented to illustrate the properties of multi-level approaches when some of the assumptions of the analytical investigation do not hold.

The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect M , X and PN (a sequence of transitions, with the first transition firable on M , such that every transition t can fire prescribed number X(t) of times). The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.

The subject of the paper is to propose two approximation algorithms FM_SPLA, FM_DPLA for priority-list scheduling in timed Petri nets. Their capability is compared with that of existing algorithms SPLA, DPLA through experimental results, where SPLA and DPLA have previously been proposed by the authors.

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

Principal Component Analysis (PCA) is a useful technique in feature extraction and data compression. It can be formulated as a statistical constrained maximization problem, whose solution is given by unit eigenvectors of the data covariance matrix. In a practical application like image compression, the problem can be solved numerically by a corresponding gradient ascent maximization algorithm. Such on-line algoritms can be good alternatives due to their parallelism and adaptivity to input data. The algorithms can be implemented in a local and homogeneous way in learning neural networks. One example is the Subspace Network. It is a regular layer of parallel artificial neurons with a learning rule that is completely homogeneous with respect to the neurons. However, due to the complete homogeneity, the learning rule does not converge to the unique basis given by the dominant eigenvectors, but any basis of this eigenvector subspace is possible. In many applications like data compression, the subspace is not sufficient but the actual eigenvectors or PCA coefficient vectors are needed. A new criterion, called the Weighted Subspace Criterion, is proposed, which makes a small symmetry-breaking change to the Subspace Criterion. Only the true eigenvectors are solutions. Making the corresponding change to the learning rule of the Subspace Network gives a modified learning rule, which can be still implemented on a homogeneous network architecture. In learning, the weight vectors will tend to the true eigenvectors.