We have devised a polynomial time algorithm to decide the security of cryptographic protocols formally under certain conditions, and implemented the algorithm on a computer as a supporting system for deciding the security. In this paper, a useful approach is presented to decide security problems which do not satisfy some of the above-mentioned conditions by using the system. For its application, we consider a basic security problem of Kerberos protocol, whether or not an enemy can obtain the session key between a client and a server by using any information not protected in communication channels and using any operation not prohibited in the system. It is shown that Kerberos is secure for this problem.

A simple algorithm is proposed for representing nonseparable functions by equivalent separable functions. In this algorithm, functions are first represented by computational graphs, which are directed graphs representing the computational process of the functions. Then, the vertices of the computational graphs are searched in preorder or postorder, and the transformation to separable forms is performed at the places where it is necessary. By this repetition of the transformation, nonseparable functions are represented by separable functions automatically. The proposed algorithm will be useful in various fields of science and engineering because funcutions of one variable are easy to deal with.

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 market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.

In this paper, we propose a timing constrained database system which accesses a database at a host computer via a mobile support server with a wireless portable computer running in mobile computing environments, so that we can provide seamless database access between a communication cell and the host computer even if the user of the portable computer moves from one communication cell to another. Then, we also provide some new kind of database cache algorihm, such as all-cell-cache, neighbour-cell-cache, 1-cell-skip-cache, 2-cell-skip-cache and 3-cell-skip-cache methods, each of which manages the data downloading and uploading among the host database and some cell databases at the mobile support servers so as to minimize the database access fault probability when the user moves from one communication cell to another. And, we show the averaged database access time and the averaged database cache hit ratio which are computed by simulating each of the above database cache algorithms with random variables generation method. Finally, we conclude that each above cache alogorithm is advantageous to the database in mobile computineg einvironments.

In this paper, we propose an analytic model using a semi-markov process for parallel computers which provides hardware support for a cache coherence mechanism. The model proposed here, the Semi-markov Memory and Cache coherence Interference model, can be used for the performance prediction of cache coherence based parallel computers since it can be easily applied to descriptions of the waiting states due to network contention or memory interference of both normal data accesses and cache coherence requests. Conventional analytic models using stochastic processes to describe parallel computers have the problem of numerical explosion in the number of states necessary as the system size increases even for simple parallel computers without cache coherence mechanisms. The number of states required by constructing our proposing analytic model, however, does not depend on the system size but only on the kind of cache coherence protocol. For example, the number of states for the Synapse cache coherence protocol is only 20, as is described in this paper. Using the proposed analytic model, we investigate several comparative experiments with widely known simulation results. We found that there is only a 7.08% difference between the simulation and our analytic model, while our analytic model can predict the performance of a 1,024 processor system in the order of microseconds.

We present a volume rendering algorithm which renders images at approximately two to seven times the speed of a conventional ray caster with almost no visible loss of image quality. This algorithm traverses the volume data in object order and renders the image by performing ray casting for the pixels within the footprint of the voxel (i.e., rectangular prism) being processed. The proposed algorithm supports the rendering of both single and multiple isosurfaces with arbitrary opacity values. While the projection approach to volume rendering is not new, we present an algorithm specifically designed for the perspective projection, evaluate its rendering speed for both single and multiple isosurfaces with arbitrary opacity values, and examine how efficiently it uses cache memory.

String grammars (languages) have been extensively studied from the 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of a context-free language to the surface set. Here the grammar regarded a tree as an input sentence to some transducer. After that from the second half of 60's, the studies of acceptors, transducers, and so on, whose inputs are trees, have been done extensively. Recently pushdown tree automata were introduced, and their fundamental and some other various properties were investigated [12],[13],[22]-[26]. Furthermore a top-down pushdown tree transducer (t-PDTT for short), which is an extension of a top-down pushdown automaton (t-PDTA for short), was introduced and its fundamental properties were investigated [27]. In this paper we focus on t-PDTT, linear t-PDTT, t-FST (top-down finite state transducer), and t-PDTA. The main subjects discussed here are as follows: (1) the class of domain/surface tree languages of t-PDTT properly contains the class of tree languages accepted by t-PDTA, (2) the class of domain/surface tree languages of linear t-PDTT's coincides with the class of tree languages accepted by t-PDTA's, (3) the class of tree languages accepted by t-PDTA's properly contains the class of surface tree languages of t-FST's.

Full-search block-matching motion estimation is a popular method to reduce temporal redundancies in video sequence. Due to its excessive computational load, parallel processing architectures are often required for real-time processing. One of the architectures is Hsieh's architecture based on systolic array processor and shift register arrays. Serial input characteristic of his scheme can reduce the number of pixel inputs to one, at the expense of significantly increasing the initialization time. This paper presents a modified and generalized Hsieh's architecture to reduce the initialization time. The proposed architecture can easily control data flows by rearranging shift register arrays and input-pin counts by using multiplexers on input stage, while retaining good properties of Hsieh's. The proposed architecture has the following advantages: (1) it allows controllable data inputs to save the pin counts, (2) it is flexible to the dimensional change of the search area via simple control, (3) it can operate in real time for video conference applications, and (4) it has simple and modular structure which is quite suitable for VLSI implementation. For verification of the proposed architecture, VHDL simulations are performed and some results are given.

When people watch such motion pictures as documentaries or educational-type films, it is very natural for them to be interested in moving objects in the movies and be eager to know the detailed information related to these object. Therefore, a mechanism that enables users to directly pick up object information from motion pictures is necessary to make a movie system feasible. For this reason, we are researching techniques on using objects in motion pictures as hypermedia anchors. We call a movie system that provides the above mechanism a video hypermedia system. An object in a motion picture can generally be considered as a complex object which includes many parts. To allow users to obtain information related to each part, a system must be able to provide anchors corresponding to each part in each complex object. For this, authors cannot help defining all anchors in all frames, since the visual status of each part varies from moment to moment. This paper presents our approach for managing objects in motion pictures for video hypermedia systems. The main feature of the proposed method is to apply computer graphic techniques to the defining of anchors for a complex object.

The data retention characteristics for Flash EEPROM degrade after a large number of write and erase cycles due to the increase of the tunnel oxide leakage current. This paper proposes a new write/erase method which uses a reverse polarity pulse after each erase pulse. By using this method, the leakage current can be suppressed. As a result, the read disturb time after 105cycles write/erase operation is more than 10 times longer in comparison with that of the conventional method. Moreover, using this method, the endurance cycle dependence of the threshold voltage after write and erase operation is also drastically improved.

In this paper we propose a new medical image processing system called Virtualized Endoscope System (VES)", which can examine the inside of a virtualized human body. The virtualized human body is a 3-D digital image which is taken by such as X-ray CT scanner or MRI scanner. VES consists of three modules; (1) imaging, (2) segmentation and reconstruction and (3) interactive operation. The interactive operation module has following thee major functions; (a) display of, (b) measurement from, and (c) manipulation to the virtualized human body. The user of the system can observe freely both the inside and the outside of a target organ from any point and any direction freely, and can perform necessary measurement interactively concerning angle and length at any time during observation. VES enables to observe repeatedly an area where the real endoscope can not enter without pain from any direction which the real endoscope can not. We applied this system to real 3-D X-ray CT images and obtained good result.

Neural network hardware using time-shared bus and integer representation architecture has already been fabricated and reported from the design viewpoint. However, nothing related to performance evaluation of hardware has yet been presented. Computation-speed, scalability and learning accuracy of hardware are evaluated theoretically and experimentally using a Back Propagation (BP) algorithm. In addition, a mirror-weight assignment technique is proposed for high-speed computation in the BP. NETTalk, an English-pronunciation-reasoning task, has been chosen as the target application for the BP. In the experiment, recently-developed neuro-hardware based on the above architecture and its parallel programming language are used. An outline of the language is described along with BP programming. Mirror-weight assignment allows maximum speed at 55.0 MCUPS (Million Connections Updated Per Second) using 256 neurons in the hidden-layer (numbers of neurons in input-and output-layers are fixed at 203 and 26 respectively in NETTalk). In addition, if scalability is defined as a function of the number of neurons in the hidden-layer, the machine retains high scalability at 0.5 if such a maximum speed needs to be used. No degradation in learning accuracy occurs when experimental results computed using the neuro-hardware are compared with those obtained by floating-point representation architecture (workstation). The experiment indicates that the present integer representational design of the neuro-hardware is sufficient for NETTalk. Performance has been evaluated theoretically. For evaluation purposes, it is assumed that most of the total execution-time is taken up by bus cycles. On the basis of this assumption, an analytical model of computation-speed and scalability is proposed. Analytical predictions agreed well with experimental results.

Three dimensional model based coding methods are proposed as next generation image coding methods. These new representations need 3D reconstruction techniques. This paper presents a method that extracts the surfaces of static objects that occlude other objects from a spatiotemporal image captured with straight-line camera motion. We propose the concept of occlusion types and show that the occlusion types are restricted to only eight patterns. Furthermore, we show occlusion type pairs contain information that confirms the existence of surfaces. Occlusion information gives strong cues for segmentation and representation. The method can estimate not only the 3D positions of edge points but also the surfaces bounded by the edge points. We show that combinations of occlusion types contain information that can confirm surface existence. The method was tested successfully on real images by reconstructing flat and curved surfaces. Videos can be hierarchically structured with the method. The method makes various applications possible, such as object selective image communication and object selective video editing.

A new global method for constructing a C2 piecewise quartic polynomial curve is presented. The coefficient matrix of equations which must be solved to construct the curve is tridiagonal. The joining points of adjacent curve segments are the given data points. The constructed curve reproduces exactly a polynomial of degree four or less. The results of experiments to test the efficiency of the new method are also shown.

Processor networks connected by buses have attracted considerable attention. Since a reconfigurable array is more powerful than a PRAM and more practical, it becomes the focus of attention. The Processor Array with Reconfigurable Bus System (PARBS) and the Reconfigurable Multiple Bus Machine (RMBM) are both models of parallel computation based on reconfigurable bus and processor array. The PARBS is a processor array that consists of processors arranged to a 2-dimensional grid with a reconfigurable bus system. The RMBM is also made of processors and reconfigurable bus system, but the processors are located in a row and the number of processors and the number of buses are independent of each other. Four versions of RMBM has been proposed and Extended RMBM (E-RMBM) is regarded as the most powerful one among them. In this paper, we describe that a PARBS of size N M can be simulated in constant time by a E-RMBM of 4NM processors, M + 3 buses and 1 read buffer, and that a E-RMBM of P processors, B buses and D read buffers can be also simulated in constant time by a PARBS of size B P. A PARBS or RMBM that solves a computational problem of size n is polynomially bounded iff the product of the number of processors and buses and red and write ports is O (nc), for some constant c. When a PARBS is polynomially bounded, the E-RMBM which simulates it is also polynomially bounded, and vice versa.

This paper examines the feasibility of a high frequency (moro than 1 GHz) ring-oscillator-type CMOS VCO, able to maintain a good linearity between the oscillator output frequency and control voltage, while preserving low voltage and low power operation capabilities. A CMOS VCO circuit, with a newly developed corrent-controlled delay cell and an architecture combining the transitions of each delay cell output, with high-frequency operation, was designed and simulated using the CMOS 0.6 µm device paramenters. We analyzed the generation of unnecessary harmonics and sub-harmonics when a delay cell's propagation delay time varied. The simulation indicated that a CMOS VCO with a frequency range of 200 MHz to 1.4 GHz, a power dissipation of 8.5 mW at 900 MHz from a 3 V power supply, and an operation voltage of 1 V to 3 V can be implemented on a chip.

This paper discusses visualization of temporal and spatial information in natural language descriptions (NLDs), focusing on the translation process of intermediate representations of NLDs to proper scenarios" and environments" for animations. First, the intermediate representations are shown according to the idea of actors. Actors and non-actors are represented as primitives of objects, whereas actions as those of events. Temporal and spatial constraints by a given NLD text are imposed upon the primitives. Then, the representations containing unknown temporal or spatial parameters --time and coordinates-- are translated into evaluation functions, where the unlikelihood of the deviations from the predicted temporal or spatial relations are estimated. Particularly, the functions concerning actor's movements contain both temporal and spatial parameters. Next, the sum of all the evaluation functions is minimized by a nonlinear optimization method. Thus, the most proper actors' time-table, or scenario, and non-actors' location-table, or environment, for visualization are obtained. Implementation and experiments show that both temporal and spatial information in NLDs are well connected through actors' movements for visualization.

Handwritten character recognition has been increasing its importance and has been expanding its application areas such as office automation, postal service automation, automatic data entry to computers, etc. It is challenging to develop a handwritten character recognition system with high processing speed, high performance, and high portability, because there is a trade-off among them. In current technology, it is difficult to attain high performance and high processing speed at the same time with single algorithms, and therefore, we need to find an efficient way of combination of multiple algorithms. We present an engineering solution to this problem. The system is based on multi-stage strategy as a whole: The first stage is a simple, fast, and reliable recognition algorithm with low substitution-error rate, and data of high quality are recognized in this stage, whereas sloppily written or degraded data are rejected and sent out to the second stage. The second stage is composed of a sophisticated structural pattern classifier and a pattern matching classifier, and these two complementary algorithms run in parallel (multiple expert approach). We demonstrate the performance of the completed system by experiments using real data.

The problem of genetic algorithm's efficiency has been attracting the attention of genetic algorithm community. Over the last decade, considerable researches have focused on improving genetic algorithm's performance. However, they are generally under the framework of natural evolutionary mechanism and the major genetic operators, crossover and mutation, are activated by the prior probabilities. An operator based on a prior probability possesses randomness, that is, the unexpected individuals are frequently operated, but the expected individuals are sometimes not operated. Moreover, as the evaluation function is the link between the genetic algorithm and the problem to be solved, the evaluation function provides the heuristic information for evolutionary search. Therefore, how to use this kind of heuristic information (present and past) is influential in the efficiency of evolutionary search. This paper, as an attempt, presents a eugenics-based genetic algorithm (EGA) -- a genetic algorithm that reflects the human's decision will (eugenics), and fully utilizes the heuristic information provided by the evaluation function for the decisions. In other words, EGA = evolutionary mechanisms + human's decision will + heuristic information. In EGA, the ideas of the positive eugenics and the negative eugenics are applied as the principle of selections and the selections are not activated by the prior probabilities but by the evaluation values of individuals. A method of genealogical chain-based selection for mutation is proposed, which avoids the blindness of stochastic mutation and the disruptive problem of mutation. A control strategy of reasonable competitions is proposed, which brings the effects of crossover and mutation into full play. Three examples, the minimum problem of a standard optimizing function--De Jong's test function F2, a typical combinatorial optimization problem--the traveling salesman problem, and a problem of identifying nonlinear system, are given to show the good performance of EGA.

Asynchronous Transfer Mode (ATM) is a promised bearer transmission service for high speed multimedia LAN. Recently, high speed multimedia ATM LAN products have been available. Therefore, in order to interconnect them, the multimedia backbone LAN, which has the expandable high throughput over 10Gbps, supporting multicast, multi-QoS, and many interfaces including 622 Mbps, will be widely required. In this paper, the VLSI oriented input and output buffered switch architecture is proposed as the hardware architecture for multimedia backbone switch node. This paper describes that the chip set consisting of four VLSIs, that is, the switch element, the switch access, the distributor/arbiter, and the multiplexer/demultiplexer, can realize the backbone switch core, and the main specifications required to each VLSI are derived.