The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)^s[NH(k)^s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)^s[NSeH(k)^s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)^s[NH(k)^s] H(k1)^s[NH (k1)^s] and SeH (k)^s[NSeH(k)^s] SeH(k1)^s[NSeH(k1)^s] hold for all k1.

By a measure we mean a function µ from {0, 1}^* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}^*). A malign measure is a measure such that if an input x in {0, 1}ⁿ (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}ⁿ) then the worst-case computation time t^WO_A (n) and the average-case computation time t^av,µ_A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.

The main result of this paper is an almost-everywhere hierarchy theorem for nondeterministic space that is as tight as the well-known infinitely-often hierarchy theorems for deterministic and nondeterministic space. In addition, we show that the complexity-theoretic notion of almost-everywhere complex functions is identical to the recursion-theoretic notion of bi-immune sets in the nondeterministic space domain. Finally, we investigate bi-immunity in nondeterministic and alternating time complexity classes and derive a similar hierarchy result for alternating time.

Behavior modeling of objects is critical in object-oriented design. In particular, it is essential to preserve integrity constraints on object behavior in application environments where objects of various classes dynamically interact with each other. In order to provide a stable design technique, a behavior model using the notion of the life cycle schema of a class is proposed. To model the aspect of behavioral abstraction of objects, the notion of schema refinement together with a diagrammatic representation technique is also defined. In this framework, a formalization of behavior constraints on objects which interact with each other is proposed together with its graphical representation. Verification rules of consistency of behavior constraints are also discussed. In order to perform certain functions, several partner objects of the same or different classes should collaborate establishing client-server relationships. The contract of a class is defined as a collection of responsibilities of a server class to a client class where each responsibility is specified in the form of the script. To achieve a high degree of systems integrity, a procedure to derive scripts from behavior constraints on collaborating partners is developed. It is also critical to evenly distribute responsibilities to partner objects. A delegation is placing a whole or a part of responsibilities of an object in charge of other objects. Based on the design principle delegation along the aggregation hierarchy,' a unified design approach to delegation that enables to reorganize scripts in constraints preserving way is proposed.

Existing algorithmic debugging methods which can locate faults under the guidance of a system have a number of shortcomings. For example, some cannot be applied to imperative languages with side effects; some can locate a faulty function but cannot locate a faulty statement; and some cannot detect faults related to missing statements. This paper presents an algorithmic critical slice-based fault-locating method for imperative languages. Program faults are first classified into two categories: wrong-value faults and missing-assignment faults. The critical slice with respect to a variable-value error is a set of statements such that (1) a wrong-value fault contained in any instruction in the critical slice may have caused that variable-value error, and (2) a wrong-value fault contained in any instruction outside the critical slice could never have caused that variable-value error. The paper also classifies errors found during program testing into three categories: wrong-output errors, missing-output errors, and infinite-loop errors with no output. It finally shows that it is possible to algorithmically locate any fault, including missing statements, for each type of error.

In using a natural language database interface (NLI) to access the contents of a databese, the user queries may contain terms that do not appear at all in both the NLI lexicon and the database. A friendly NLI should not reject user queries with unknown terms, but should be able to handle them, and should be able to learn new lexical items. Such capability increases the usefulness of the NLI, and allows the NLI to more cover the domain of the underlying database. Therefore, a technique to handle unknown terms is decisive in designing a friendly NLI. In this work, we discuss a method that would allow a NLI to identify the meanings of unknown database field values, and terms that are exceeding the conceptual coverage of the database, in the user queries, by engaging the user in clarification dialogues based on a database-domain hierarchy. It will be shown that the method enables the NLI lexicon to learn new lexical items at run time while the clarification dialogues, and it may provide the necessary information for generating informative answers to some particular failing user queries. Moreover, the method is an efficient means to handle queries with insufficience contextual cues. The examples throughout this work are drawn from FIFA 90, an experimental NLI to a soccer database.

In the applications of the fast Fourier transform (FFT) to real-world computation such as robot vision, high-speed processing with small latency is an important issue. In this paper, we propose a linear array processor for the minimum-latency FFT computation. The processor is constructed by identical butterfly elements (BE's). The key concept to minimize the latency is that each BE generates its output data immediately after its input data become available, with 100% utilization of its arithmetic unit. We also introduce the real-valued FFT to perform the complex-valued FFT. We utilize a double linear array structure so that the parallel processing can be realized without communication between the linear arrays. As a result, the hardware amount of a single BE is reduced to half that of conventional designs. The latency of the proposed FFT processor is greatly reduced in comparison with conventional linear array FFT processors.

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.

The self-organizing feature map is one of the most widely used neural network paradigm based on unsupervised competitive learning. However, the learning algorithm introduced by Kohonen is very slow when the size of the map is large. The slowness is caused by the search for large map in each training steps of the learning. In this paper, a fast learning algorithm based on incremental ordering is proposed. The new learning starts with only a few units evenly distributed on a large topological feature map, and gradually increases the number of units until it covers the entire map. In middle phases of the learning, some units are well-ordered and others are not, while all units are weekly-ordered in Kohonen learning. The ordered units, during the learning, help to accelerate the search speed of the algorithm and accelerate the movements of the remaining unordered units to their topological locations. It is shown by theoretical analysis as well as experimental analysis that the proposed learning algorithm reduces the training time from O(M²) to O(log M) for M by M map without any additional working space, while preserving the ordering properties of the Kohonen learning algorithm.

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

In the field of computer vision the detection of edges in an image serves to simplify the date in the early stages, into a form which is more easily processed by the computer. But because of noise or due to the inherent weaknesses of the chosen edge detector, gaps or interruptions in the edges may be formed. In order for further processing to proceed with accuracy and confidence, these gaps must be filled or linked to form a more continuous edge. Proposed in this paper is a unique method of edge linking. This method consists of three steps, labelling, linking and merging. The procedure makes use of global information in the labelling process and local information with the use of templates in the linking and merging processes. As a result of the unique way in which the gaps between edge segments are filled, distortion of the edge image is kept minimal. One other advantage of the proposed edge linker is that it can be used in combination with different edge detection schemes. To show the effectiveness of the proposed method, comparisons are given. These include the linear feature extraction method of Zhou et.al., upon which the proposed method is based and also outputs from a method described by Nevatia.

High-speed learning of neural networks using the multifrequency oscillation method is demonstrated for first time. During the learning of an analog neural network integrated circuit implementing the exclusive-OR' logic, weight and threshold values converge to steady states within 2 ms for a learning speed of 2 mega-patterns per second.