This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (witness) that disproves the inclusion for a pair of real-time droca's which accept by final state, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.

The investigation of device functions required from the systems point of view will be important for the development of the next generation of VLSI devices and systems. In this paper, a super pass transistor (SPT) model is presented as a quantum device candidate for future VLSI systems based on multiple-valued logic. A possible quantum device structure for the SPT model is also described, which employs the concepts of a lateral-resonant-tunneling quantum-dot transistor and a heterostructure field-effect transistor. Since it has the powerful capability of detecting multiple signal levels, the SPT will be useful for the implementation of highly compact multiple-valued VLSI systems. To exploit the functionality of the SPT, a super pass gate (SP-gate) corresponding to a single SPT is proposed as a multiple-valued universal logic module. The mathematical properties of the SP-gate are discussed. A design method for a multiple-valued SP-gate network is presented. An application of SP-gates to a multiple-valued image processing system is also demonstrated. The SP-gate network for the multiple-valued image processing system is evaluated in comparison with the corresponding NMOS implementation in terms of the number of transistors, interconnections and cascaded transistor stages. The size of a generalized series-parallel SP-gate network is also evaluated in comparison with a functionally equivalent multiple-valued series-parallel MOS pass transistor network. The results show that highly compact multiple-valued VLSI systems can be achieved if the SPT-model can be realized by an actual quantum device.

Data flow is a paradigm for concurrent computations in which a collection of parallel processes communicate asynchronously. For nondeterministic data flow networks many semantic models have been defined, however, it is complex to reason about the semantics of a network. In this paper, we introduce a transformation between data flow networks and the LOTOS specification language to make available theories and tools developed for process algebras for the semantic analysis based on traces of the networks. The transformation does not establish a one-to-one mapping between the traces of a data flow network and the LOTOS specification, but maps each network in a specification which usually contains more traces. The obtained system specification has the same set of traces as the corresponding network if they are finite, otherwise also non fair traces are included. Formal analysis and verification methods can still be applied to prove properties of the original data flow network, allowing in case of networks with finite traces to prove also network equivalence.

We have designed and implemented a simple yet powerful declarative synchronization mechanism for a paralle object-oriented computation model. The mechanism allows the user to control multiple message reception, specify the order of message reception, lock an invocation, and specify relations as invocation constraints. It has been included in a parallel object-oriented language, called A-NETL. The compiler and operating system have been developed on a total architecture, A-NET (Actors NETwork). The experimental results show that (i) the mechanism allows the user to model asynchronous events naturally, without losing the integrity of described programs; (ii) the replacement of the mechanism with the user's code requires tedious descriptions, but gains little performance enhancement, and certainly loses program readability and integrity; (iii) the mechanism allows the user to shift synchronous programs to asynchronous ones, with a scalable reduction of execution times: an average 20.6% for 6 to 17 objects and 46.1% for 65 objects. These prove the effectiveness of the proposed synchronization mechanism.

A bottleneck identification methodology is proposed for the performance-oriented design of shared-bus multiprocessors, which are composed of several major subsystems (e.g. off-chip cache, bus, memory, I/O). A subsystem with the longest access time per instruction is the one that limits processor performance and creates a bottleneck to the system. The methodology also facilitates further refined analysis on the access time of the bottleneck subsystem to help identify the causes of the bottleneck. Example performance model of a particular shared-bus multiprocessor architecture with separate address bus and data bus is developed to illustrate the key idea of the bottleneck identification methodology. Accessing conflicts in subsystems and DMA transfers are also considered in the model.

The purpose of this research is to analyze production rules with coupling modes in active databases and to exploit an assistant system for rule programming. Each production rule is a specification including an event, a condition, and an action. The action is automatically executed whenever the event occurs and the condition is satisfied. Coupling modes are useful to control execution order of transactions. For example, a transaction for consistency check should be executed after transactions for update. An active database, which is a database with production rules, can spontaneously update database states and check their consistency. Production rules provide a powerful mechanism for knowledge-bases. However it is very difficult in general to predict how a set of production rules will behave because of cascading rule triggers, concurrency, and so on. We are attempting to adopt a process algebra as a basic tool to analyze production rules. In order to describe and analyze concurrent and communicating systems, process algebras such as CCS, CSP, ACP, and π-calculus, are well known. However there are some difficulties to apply existing process algebras to analysis of production rules in growing process trees by process creation. In this paper we propose a process algebra named CCSPR (a Calculus of Communicating Systems with Production Rules), Which is an extension of CCS. An advantage of CCSPR is to syntactically describe growing process trees. Therefore, production rules can be appropriately analyzed in CCSPR. After giving definitions and properties of CCSPR, we show an example of analysis of production rules in CCSPR.

This paper presents a comprehensive framework for the organization, retrieval, and adaptation of image information and meta-information in image database systems. The multi-level hierarchy of images that emphasizes the composition of visual entities (such as Human, Chair, , etc.) from its constituents (eye, leg, , etc.) is managed by a host architecture that is called the semantic tree. This architecture is shown to integrate description, numeric, and statistic image constituent's information into a compound space that is used as retrieval basis for semantic, sketch, and template image queries and several other composite query types. The core architecture based on which the semantic tree is constructed is shown to offer several new features such as simple prototyping, complex prototyping, low storage requirements, and automatic knowledge acquisition compatibility. The object oriented data model constitutes our comparison basis throughout the paper. Methods (functions) used to access image information are shown to be organized into a separate architecture called the query dictionary. This architecture is shown to offer a convenient hierarchical message passing medium using which a variety of composite queries are constructed. Interaction between semantic trees and the query dictionary is clarified through several examples. It is shown that the semantic tree architecture embraces additional networking semantic intormation through a range of relation representation models, the first of which is introduced in this paper. A new inheritance method called semantic relation spreading is introduced. Comprehensive examples are given to demonstrate the versatility of the new strategy.

Distributed computing over a network of workstations continues to be an illusive goal. Its main obstacle is the delay penalty due to network protocol and OS overhead. We present in this paper a low level hardware supported scheme for managing distributed shared memory (DSM), as an underlying paradigm for distributed computing. The proposed DSM is novel in that it employs a two-tier paging scheme that reduces the probability of false sharing and facilitates an efficient hardware implementation. The scheme employs a standard OS page and divides it into fixed smaller memory units called paragraphs, similar to cache lines. This scheme manages the shared data regions only, while other regions are handled by the OS in the standard manner without modification. A hardware extension of a traditional MMU, namely Distributed MMU or DMMU, is introduced to support the DSM. Shared memory coherency is maintained through a write-invalidate protocol. An analytical model is built to evaluate the system sensitivity to various parameters and to assess its performance.

Keyword spotting is a fundamental approach to recognizing/understanding naturally and spontaneously spoken language. To spot acoustic events such as keywords, an overall spotting system, comprising acoustic models and decision thresholds, primarily needs to be optimized to minimize all spoting errors. However, in most conventional spotting systems, the acoustic models and the thresholds are separately and heuristically designed: There has not necessarily been a theoretical basis that has allowed one to design an overall system consistently. This paper introduces a novel approach to spotting, by proposing a new design method called Minimum SPotting Error learning (MSPE). MSPE is conceptually based on a recent discriminative learning theory, i.e., the Minimum Classification Error learning/Generalized Probabilistic Descent method (MCE/GPD); it features a rigorous framework for minimizing spotting error objectives. MSPE can be used in a wide range of pattern spotting applications, such as spoken phonemes, written characters as well as spoken words. Experimental results for a Japanese consonant spotting task clearly demonstrate the promising future of the proposed approach.

This paper proposes an unsupervised speaker adaptation method using an all-phoneme ergodic Hidden Markov Network" that combines allophonic (context-dependent phone) acoustic models with stochastic language constraints. Hidden Markov Network (HMnet) for allophone modeling and allophonic bigram probabilities derived from a large text database are combined to yield a single large ergodic HMM which represents arbitrary speech signals in a particular language so that the model parameters can be re-estimated using text-unknown speech samples with the Baum-Welch algorithm. When combined with the Vector Field Smoothing (VFS) technique, unsupervised speaker adaptation can be effectively performed. This method experimentally gave better performances compared with our previous unsupervised adaptation method which used conventional phonetic HMMs and phoneme bigram probabilities especially when the amount of training data was small.

A computer-based system for the automatic determination of the physical parameters of rainfall was developed. The measuring device consists of a light source and two TV cameras. Images of raindrops that fell through the slit were observed on a frosted glass plate as shadow images which were photographed simultaneously by two TV cameras with different shutter speeds and analyzed. The data indicated that the shape of raindrops were spheroid in case of small diameter but were slightly deformed into an oblate spheroid in case of larger diameter, and the fall velocity tends to increase with increasing size of raindrops. Rainfall rates calculated from the shape and velocity were compared with those measured directly and found to agree.

In case of object recognition using 3-D configuration data, the scale and poses of the object are important factors. If they are not known, we can not compare the object with the models in the database. Hence we propose a strategy for object recognition independently of its scale and poses, which is based on Hopfield neural network. And we also propose a strategy for estimation of the camera motion to reconstruct 3-D configuration of the object. In this strategy, the camera motion is estimated only with the sequential images taken by a moving camera. Consequently, the 3-D configuration of the object is reconstructed only with the sequential images. And we adopt the multiple regression analysis for estimation of the camera motion parameters so as to reduce the errors of them.

This paper presents a system for recognition of on-line cursive Hangul (Korean characters) by means of DP matching of structural information. The penalty function has the following special features. In order to prevent short spurious strokes from causing large penalties, an input stroke is weighted by its length relative to other input strokes. In order to make use of pen-up and pen-down information, a penalty is incurred when 2 strokes of differing type (i.e. pen-up with pen-down) are matched. Finally, to reduce the chance of obtaining a suboptimal solution which can result from using the greedy algorithm in DP matching, we look-ahead an extra match. In a computer simulation we obtained a recognition rate of 92% for partially cursive characters and 89% for fully cursive characters. Furthermore, for both cases combined the correct character appears 98% of the time in the top 10 candidates. Thus we confirmed that the proposed algorithm is effective in recognizing cursive Hangul.

This paper presents a theoretically best algorithm within the framework of our image noise model for reconstructing 3-D from two views when all the feature points are on a planar surface. Pointing out that statistical bias is introduced if the least-squares scheme is used in the presence of image noise, we propose a scheme called renormalization, which automatically removes statistical bias. We also present an optimal correction scheme for canceling the effect of image noise in individual feature points. Finally, we show numerical simulation and confirm the effectiveness of our method.

The back-propagation algorithm has been applied to many fields, and has shown large capability of neural networks. Many people use the back-propagation algorithm together with a momentum term to accelerate its convergence. However, in spite of the importance for theoretical studies, theoretical background of a momentum term has been unknown so far. First, this paper explains clearly the theoretical origin of a momentum term in the back-propagation algorithm for both a batch mode learning and a pattern-by-pattern learning. We will prove that the back-propagation algorithm having a momentum term can be derived through the following two assumptions: 1) The cost function is Eⁿα^n-µE_µ, where E_µ is the summation of squared error at the output layer at the µth learning time and a is the momentum coefficient. 2) The latest weights are assumed in calculating the cost function Eⁿ. Next, we derive a simple relationship between momentum, learning rate, and learning speed and then further discussion is made with computer simulation.

The electroretinogram (ERG) is used to diagnose many kinds of eye diseases. Our final purpose in this paper is a detection of diabetic retinopathy by using only ERG. In this paper, we describe a method to examine whether presented ERG data belong to a group of diabetic retinopathy. The ERG mainly consists of the a-wave, the b-wave and the oscillatory potential (op-wave). It was known that the op-wave varies as progress of retinopathy. Thus, we use the latency, the amplitude and the peak frequency of the op-wave. First, we study these features of sample ERG data, statistically. It was clarified that some of these characteristics are significantly different between a normal group and a group of diabetic retinopathy. By using some of these characteristics, we classify unknown ERG data on the basis of the Mahalanobis' generalized distance or the linear discriminant function. The highest accuracy of this method for the unknown data is about 92.73%.