For two finite disjoint sets P and Q of strings over an alphabet Σ, an alphabet indexing for P, Q by an indexing alphabet Γ with |Γ||Σ| is a mapping :ΣΓ satisfying (P)(Q), where :Σ*Γ* is the homomorphism derived from . We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.

Graph unification is doubtlessly the most expensive process in unification-based grammar parsing since it takes the vast majority of the total parsing time of natural language sentences. A parsing time overload in unification consists in that, in general, no less than 60% of the graph unifications performed actually fail. Thus one way to achieve unification time speed-up is focusing on an efficient, fast way to deal with such unification failures. In this paper, a process, prior to unification itself, capable of filtering or stopping a considerably high percentage of graphs that would fail unification is proposed. This unification-filtering process consists of comparison of signatures that correspond to each one of the graphs to be unified. Unification-filter (hereafter UF) is capable of stopping around 87% of the non-unifiable graphs before unification itself takes place. UF takes significantly less time to detect graphs that do not unify and discard them than it would take to unification to fail the attempt to unify the same graphs. As a result of using UF, unification is performed in an around 71% of the time for the fastest known unification algorithm.

Two new algorithms for performing modular exponentiation are suggested. Nonstandard number systems are used. The first algorithm is based on the representing the exponent as a sum of generalized Fibonacci numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.

Exploiting the full potential of a multiprocessor system requires a good job scheduling algorithm. In this paper we analyze three dynamic job scheduling algorithms in multiprocessor systems. These algorithms are based on static job scheduling algorithms, LPT (longest processing time first), SJF (shortest job first), and LPR (largest processor requirement first), each of which exhibits good performance in terms of asymptotic upper bound on the makespan of the schedule generated by it. We analyze their performance in the dynamic case experimentally, where we have a stochastic stream of jobs with arbitrary processing time and processor requirement. We compare their performance with the FCFS algorithm and its simple extension. Except for LPT, the algorithms are found to perform significantly better than FCFS, while among themselves SJF performs the best, followed by K-LPR, a variation of LPR. We also consider the fairness aspect of these algorithms and propose a general technique to impose fairness on these algorithms. Finally, we analyze the impact of imposing fairness on the performance of these algorithms.

We introduce the interval set of a graph G which is a representation of the proper-path-decomposition of G, and show a linear time algorithm to construct an optimal interval set for any tree T. It is shown that a proper-path-decomposition of T with optimal width can be obtained from an optimal interval set of T in O(n log n) time.

This paper proposes a new environment for high-level VLSI design specification validation using "Algorithmic Debugging" and evaluates its benefits on three significant examples (a protocol processor, an 8-bit CPU, and a Prolog processor). A design is specified at a high-level using the structured analysis (SA) method, which is useful for analyzing and understanding the functionality to be realized. The specification written in SA is transformed into a logic programming language and is simulated in it. The errors (which terminate with an incorrect output in the simulation) included in the three large examples are efficiently located by answering junt a few queries from the algorithmic debugger. The number of interactions between the designer and the debugger is reduced by a factor of ten to a hundred compared to conventional simulation based validation methodologies. The correct SA specification can be automatically translated into a Register Transfer Level (RTL) specification suitable for logic synthesis. In this environment, a designer is freed from the tedious task of debugging a RTL specification, and can concentrate on the design itself. This environment promises to be an important step towards efficient high-level VLSI design specification validation.

This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we propose a modified genetic channel router. We adopt the compatible crossover operator and newly designed compatible mutation operator in order to search solution space more effectively, where vertical constraints are integrated. By carefully selected fitness function forms and optimized genetic parameters, the current version speeds up benchmarks on average about 5.83 times faster than that of our previous version. Moreover the total convergence to optimal solutions for benchmarks can be always obtained.

This paper presents a new numerical procedure for solving the scattering wave by the moving surface. Recently, the author and her colleagues have proposed a novel numerical procedure of grid generation having a coordinate line coincident with an arbitrarily shaped moving boundary. The time dependent curvilinear coordinate system which coincides with a contour of moving boundary in a physical region is transformed into fixed rectangular coordinate system. The simple form for the transformation is made possible to choose the function between the physical region and the rectangular computational region. The FD-TD algorithm is exactly solved in this fixed rectangular coordinate system. In this paper, for the application of the FD-TD algorithm to the body fitted grid generation with moving boundary, the stability criterion of FD-TD algorithm for the body fitted grid generation with moving boundary in three dimensions is derived. The stability criterion is shown an upper bound for time step assuring stable numerical solutions. The study of scattering of electromagnetic and acoustic wave from a moving or a rotating body is very important for electromagnetic probing of moving body. The problem has been investigated in the past by numerous authors. One of them is solved by FD-TD method, where the linear interpolation is introduced for the movement. By using the presented transformation technique where time component is added to the grid generation, the time depending coordinate system can be transformed into fixed rectangular coordinate system. Then the problems are directly solved by FD-TD method in the transformed coordinate system. To verify this numemical technique, scattered field is evaluated in the case when a plane wave is normally incident on a moving perfectly conducting flat plate. The numerical results are compared with the exact ones and excellent agreement between them is obtained.

In general, message passing multiprocessors suffer from communication overhead and shared memory multiprocessors suffer from memory contention. Also, data I/O overhead limits performance. In particular, computer vision tasks that require massive computation are strongly affected by these disadvantages. This paper proposes new parallel architectures for computer vision, a Flexibly (Tightly/Loosely) Coupled Multiprocessor (FCM) and a Flexibly Coupled Hypercube Multiprocessor (FCHM) to alleviate these problems. FCM and FCHM have a variable address space memory in which a set of neighboring memory modules can be merged into a shared memory by a dynamically partitionable topology. FCM and FCHM are based on two different topologies: reconfigurable bus and hypercube. The proposed architectures are quantitatively analyzed using computational models and parallel vision algorithms are simulated on FCM and FCHM using the Intel's Personal SuperComputer (iPSC), a hypercube multiprocessor, showing significant performance improvements over that of iPSC.

We present a novel algorithm to reconstruct the refractive-index profile of a circularly symmetric object from measurements of the electromagnetic field scattered when the object is illuminated by a plane wave. The reconstruction algorithm is besed on an iterative procedure of matching the scattered field calculated from a certain refractive-index distribution with the measured scattered field on the boundary of the object. In order to estimate the convergence of the reconstruction, the mean square error between the calculated and measured scattered fields is introduced. It is shown through reconstructing several examples of lossy dielectric cylinders that the algorithm is quite stable and is applicable to high-contrasty models in situations where the Born approximation is not valid.

A method is presented for reconstructing the surface profile of a perfectly conducting rough surface boundary from the measurements of the scattered far-field. The proposed inversion algorithm is based on the use of the Kirchhoff approximation and in order to determine the surface profile, the Fletcher-Powell optimization procedure is applied. A number of numerical results illustrating the method are presented.

An active contour model which is called Snakes was proposed to extract the border line of an object from an image. This method presents the minimization problem of the energy function defined on the contour curve. The authors obtained an excellent result by applying genetic algorithm to the contour extraction. In this paper, the biphased genetic algorithm, which is a new type of genetic algorithm, is proposed to minimize the energy function of Snakes. The parameters of the genetic algorithm are examined to tune up its local and global search abilities. The biphased genetic algorithm composed of two phases of genetic search is constructed to use both abilities of the exploration and the exploitation properties of the genetic algorithm. The processing results of the biphased genetic algorithm are compared with those of the previous methods, and the advantages of the proposed algorithm are shown by several experiments.

This paper proposes new real–time heuristic distributed parallel algorithms for search, which are based on the concepts of propagations and competitions of concurrent waves. These algorithms are characterized by simplicity and clearness of control strategies for search, and distinguished abilities in many aspects, such as real–time performance, wide suitability for searching AND/OR implicit graphs, and ease in hardware implementation.

This paper presents a novel and successful logic synthesis method for optimizing ternary logic functions of any given number of input variables. A new optimization algorithm to synthesize and minimize an arbitrary ternary logic function of n-input variables can always lead this function to optimal or very close to optimal solution, where [n (n1)/2]1 searches are necessary to achieve the optimal solution. Therefore, the complexity number of this algorithm has been greatly reduced from O(3n) into O(n2). The advantages of this synthesis and optimization algorithm are: (1) Very easy logic synthesis method. (2) Algorithm complexity is O(n2). (3) Optimal solution can be obtained in very short time. (4) The method can solve the interconnection problems (interconnection delay) of VLSI and ULSI processors, where very fast and parallel operations can be achieved. A transformation method between operational and polynomial domains of ternary logic functions of n-input variables is also discussed. This transformation method is very effective and simple. Design of the circuits of GF(3) operators, addition and multiplication mod-3, have been proposed, where these circuits are composed of Josephson junction devices. The simulation results of these circuits and examples show the following advantages: very good performances, very low power consumption, and ultra high speed switching operation.

A globally and quadratically convergent algorithm is presented for solving nonlinear resistive networks containing transistors modeled by the Gummel-Poon model or the Shichman-Hodges model. This algorithm is based on the Katzenelson algorithm that is globally convergent for a broad class of piecewise-linear resistive networks. An effective restart technique is introduced, by which the algorithm converges to the solutions of the nonlinear resistive networks quadratically. The quadratic convergence is proved and also verified by numerical examples.

Nonmonotonic reasoning is a logical inference system which attempts to approximate human commonsense reasoning and is characterized as defeasible: having reasonably drawn a conclusion from some premises we may be forced to retract that conclusion upon learning new facts. This paper introduces a Petri net model for nonmonotonic reasoning with nonmonotonic rules generated by annotated logic programs and the unless operator. In the Petri net model, a fixpoint of a nonmonotonic theory can be represented as a maximal and consistent support of a firing sequence. We propose a structural method for finding extensions (coherent consequences) for a given set of nonmonotonic logic rules. It is based on the T-invariant technique for testing fireability of a goal transition in the Petri net model of Horn clause logic programs.

We modified the adaptive fuzzy classification algorithm (AFC), which allows fuzzy clusters to grow to meet the demands of a given task during training. Every fuzzy cluster is defined by a reference vector and a fuzzy cluster radius, and it is represented as a shape of hypersphere in pattern space. Any pattern class is identified by overlapping plural hyperspherical fuzzy clusters so that it is possible to approximate complex decision boundaries among pattern classes. The modified AFC was applied to recognize handwritten digits, and performances were shown compared with other neural networks.

Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (CO-trees) and their computing methods. A CO-tree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between CO-trees. The time complexities to compute the distances between two CO-trees Ta and Tb are OT (N 2aN 2b) for the distance based on a TM and OT(mambNaNb) for that on an SSPM, respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The space complexities of both methods are Os(NaNb). Those distances can be applied to the clustering of CO-trees.