This paper's main objective is to clearly describe the construction of a universal code for minimizing Davisson's minimax redundancy in a range where the true model and stochastic parameters are unknown. Minimax redundancy is defined as the maximum difference between the expected persymbol code length and the per-symbol source entropy in the source range. A universal coding scheme is here formulated in terms of the weight function, i.e., a method is presented for determining a weight function which minimizes the minimax redundancy even when the true model is unknown. It is subsequently shown that the minimax redundancy achieved through the presented coding method is upper-bounded by the minimax redundancy of Rissanen's semi-predictive coding method.
This paper's main objective is to analyze several procedures which select the model g among a set G of stochastic models to minimize the value of an information criterion in the form of L(g)H[g](zn)+(k(g)/2)c(n), where zn is the n observed data emitted by an information source θ which consists of the model gθ∈G and k(gθ) mutually independent stochastic parameters in the model gθ∈G, H[g](zn) is (-1) (the maximum log likelihood value of the data zn with respect to a model g∈G), and c(n) is a predetermined function (penalty function) of n which controls the amount of penalty for increasing the model size. The result is focused on specific performances when the information criteria are applied to the framework of so-called state decomposition. Especially, upper bounds are derived of the following two performance measures for each penalty function c(n): the error probability of the model selection, and the average Kullback-Leibler information between the true information source and the estimated information source.
In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x
Bumchul KIM Michitaka KAMEYAMA Tatsuo HIGUCHI
The performance of processing elements can be improved by the progress of VLSI circuit technology, while the communication overhead can not be negligible in parallel processing system. This paper presents a unified scheduling that allocates tasks having different task processing times in multiple processing elements. The objective function is formulated to measure communication time between processing elements. By employing constraint conditions, the scheduling efficiently generates an optimal solution using an integer programming so that minimum communication time can be achieved. We also propose a VLSI processor for robotics whose latency is very small. In the VLSI processor, the data transfer between two processing elements can be done very quickly, so that the communication cycle time is greatly reduced.
Takatoshi SUGIYAMA Hiroshi KAZAMA Masahiro MORIKURA Shuji KUBOTA Shuzo KATO
This paper proposes a superposed SSMA (Spread Spectrum Multiple Access)-QPSK (Quadrature Phase Shift Keying) signal transmission scheme over high speed QPSK signals to achieve higher frequency utilization efficiency and to facilitate lower power transmitters for SSMA-QPSK signal transmission. Experimental results show that the proposed scheme which employs the coding-rate of one-half FEC (Forward Error Correction) and a newly proposed co-channel interference cancellation scheme for SSMA-QPSK signals can transmit twenty SSMA-QPSK channels simultaneously over a nonlinearly amplified high speed QPSK signal transmission channel and achieve as ten times SSMA channels transmission as that without co-channel interference cancellation when the SSMA-QPSK signal power to the high speed QPSK signal power ratio equals -30dB. Moreover, cancellation feasibility generation of the interference signals replica through practical hardware implementation is clarified.
This letter describes the usefulness of a homogeneous spherical model of the isolated human head in SAR calculation for UHF plane-wave exposure. Comparison is made between this SAR and several results that were computed and measured for the homogeneous but realistic whole-body model of the human by other researchers.
Yoshihiro MIYAKE Yoko YAMAGUCHI Masafumi YANO Hiroshi SHIMIZU
The mechanism of environment-dependent self-organization of "positional information" in a coupled nonlinear oscillator system is proposed as a new principle of realtime coordinative control in biological distributed system. By modeling the pattern formation in tactic response of Physarum plasmodium, it is shown that a global phase gradient pattern self-organized by mutual entrainment encodes not only the positional relationship between subsystems and the total system but also the relative relationship between internal state of the system and the environment.
Hiroaki NAMBU Kazuo KANETANI Youji IDEI Kunihiko YAMAGUCHI Toshirou HIRAMOTO Nobuo TAMBA Kunihiko WATANABE Masanori ODAKA Takahide IKEDA Kenichi OHHATA Yoshiaki SAKURAI Noriyuki HOMMA
A new redundancy technique especially suitable for ultra-high-speed static RAMs (SRAMs) has been developed. This technique is based on a decoding-method that uses two kinds of fuses without introducing any additional delay time. One fuse is initially ON and can be turned OFF afterwards, if necessary, by a cutting process using a focused ion beam (FIB). The other is initially OFF and can be turned ON afterwards by a connecting process using laser chemical vapor deposition (L-CVD). This technique is applied to a 64 kbit SRAM having a 1.5-ns access time. The experimental results obtained through an SRAM chip repaired using this redundancy technique show that this technique does not introduce any increase in the access time and does not reduce the operational margin of the SRAM.
Masakatsu NISHIGAKI Nobuyuki TANAKA Hideki ASAI
This paper describes a mixed mode circuit simulation by the direct and relaxation-based methods with dynamic network partitioning. For the efficient circuit simulation by the direct method, the algorithms with circuit partitioning and latency technique have been studied. Recently, the hierarchical decomposition and latency and their validities have been researched. Network tearing techniques enable independent analysis of each subnetwork except for the local datum nodes. Therefore, if the local datum nodes are also torn, each subnetwork is separated entirely. Since the network separation is based on relaxation approach, the implementation of the separation technique in the circuit simulation by the direct method corresponds to performing the mixed mode simulation by the direct and relaxation-based methods. In this paper, a dynamic "network separation" technique based on the tightness of the coupling between subnetworks is suggested. Then, by the introduction of dynamic network separation into the simulator SPLIT with hierarchical decomposition and latency, the mixed mode circuit simulator, which selects the direct method or the relaxation method and determines the block size of the latent circuit dynamically and suitably, is constructed.
Takashi AMEMIYA Hirosuke YAMAMOTO
A new class of the universal representation for the positive integers is proposed. The positive integers are divided into infinite groups, and each positive integer n is represented by a pair of integers (p,q), which means that n is the q-th number in the p-th group. It is shown that the new class includes the message length strategy as a special case, and the asymptotically optimal representation can easily be realized. Furthermore, a new asymptotically and practically efficient representation scheme is proposed, which preserves the numerical, lexicographical, and length orders.
Dong-Ik LEE Tadaaki NISHIMURA Sadatoshi KUMAGAI
Free choice nets are a class of Petri nets, which can represent the substantial features of systems by modeling both choice and concurrency. And in the modelling and design of a large number of concurrent systems, live and safe free choice nets (LSFC nets) have been explored their structural characteristics. On the other hand, state machine decomposable nets (SMD nets) are a class of Petri nets which can be decomposed by a set of strongly connected state machines (S-decomposition). State machine allocatable nets (SMA nets) are a well-behaved class of SMD nets. Of particular interest is the relation between free choice nets and SMA nets such that a free choice net has a live and safe marking if and only if the net is an SMA net. That is, the structure of an LSFC net is an SMA net. Recently, the structure of SMA net has been completely characterized by the authors based on an S-decomposition. In other words, a necessary and sufficient condition for a net to be an SMA net is obtained in terms of the net structure where synchronization between strongly connected state machine components (S-components) has been clarified. Unfortunately, it requires tremendous amount of time and spaces to decide a given net to be an SMA net by applying the condition directly. Moreover, there exist no efficient algorithm to decide the liveness and safeness of a given SMA net that lessens the usefulness of decomposition techniques. In this paper, we consider efficient polynomial order algorithms to decide whether a given net is a live and safe SHA net.
Compared to multi-level signature file techniques, PSF (Partitioned Signature File) technique has less processing overhead by its characteristics of a simple file organization. In a multi-processor environment, the PSF technique also has an advantage that queries can be processed in parallel effectively by allocating one or more partitions to each processor. Main point of the PSF technique is a partitioning scheme based on a key selection. In this paper, an n-BFK (n-Bounded Floating Key) partitioning scheme is proposed, in which the number of segments for a key selection is bounded by n. The cost model is developed for the performance evaluation of the proposed scheme. By performance comparison with the existing schemes, the efficiencies of the proposed scheme are shown with respect to a disk access cost, a signature reduction ratio, and an uniformity of workload.
Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in LPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and
In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x{0,1}*, outputs y such that (x,y)R with overwhelming probability if xdom R, and outputs "" with probability 1 if x
Fumihiko UESUGI Iwao NISHIYAMA
A new direct projection patterning technique of aluminum using synchrotron radiation (SR) is proposed. It is based on the thermal reaction control effect of SR excitation. In the case of the Si surface, pure thermal growth is possible at 200, however, this growth is suppressed perfectly by SR irradiation. On the other hand, Al growth on the SiO2 surface is impossible at the same temperature thermally, however, SR has an effect to initiate thermal reaction. Both new effects of SR, suppression and initiation, are clarified to be caused by atomic order level thin layers formed from CVD gases by SR excitation on the surfaces. By using these effects, the direct inverse and normal projection patterning of Al are successfully demonstrated.
A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.
This paper surveys modeling techniques for telephone call control based on a Finite State Machine (FSM) concept, and studies model simplification techniques. First, the basic concept and fundamental issues of call control modeling are described. Then, based on the analysis of layered call control configuration, it is clarified that the call control machine decomposition within the two-party service control layer has the effect of reducing the apparent size of each mate's machine. Using this effect, guidelines for call control modeling are derived, by which multiple services can be modeled independently. Finally implementation techniques and a few examples of application will be presented.
Heung-Shik KIM Jong-Soo PARK Myunghwan KIM
An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.
Masayuki SUGIURA Yasuhiko MATSUNAGA Kunihiro ASADA Takuo SUGANO
Among the many fabrication methods for oxide superconductor films, metal organic chemical vapor deposition (MOCVD) is particularly suitable for industrial application because of its mass productivity and the low growth temperature. Therefore we have studied this technique using the horizontal cold wall furnace type MOCVD method to obtain high quality superconducting films. As the result, we have succeeded in fabricating YBa2Cu3Oy films which have high critical temperatures (over 80 K) under substrate temperatures as low as 700 without post-annealing. But, in the course of our experiments, it was found that the thicknesses of YBa2Cu3Oy films fabricated by MOCVD were not uniform. The cause of this non-uniformity is believed to be that the deposition rate exponentially falls off along the flow direction because of the decrease of the source gas concentration through the reaction. In this paper, this non-uniformity is analytically studied. It is shown that the deposition rate decrease can be controlled with a tapered inner tube, and that these theoretical results are in good agreement with the results of experiment. In addition, it is indicated that the superconducting property of the films has less dependence on substrate position as a result of the tapered inner tube.
Hiroki ARIMURA Takeshi SHINOHARA Setsuko OTSUKI
In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.