Takafumi KANAZAWA Toshimitsu USHIO
In evolutionary game theory, to the best of our knowledge, individuals' perceptions have not been taken into consideration explicitly. When an individual interacts with the other individual under coexistence of heterogeneous sub-populations, the individual may be willing to change his/her strategy depending on the sub-population the other individual belongs to. Moreover, in such a situation, each individual may make an error about the sub-population the other individual belongs to. In this paper, we propose a multi-population model with such erroneous perceptions. We define an evolutionarily stable strategy (ESS) and formulate replicator dynamics in this model, and prove several properties of the proposed model. Moreover, we focus on a two-population chicken game with erroneous perceptions and discuss characteristics of equilibrium points of its replicator dynamics.
Tomohiko UYEMATSU Fumio KANAYA
This paper considers the universal coding problem for stationary ergodic sources with countably infinite alphabets. We propose modified versions of LZ77 and LZ78 codes for sources with countably infinite alphabets. Then, we show that for any source µ with Eµ[log X1]<∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that we can modify LZ77 and LZ78 codes so that both are asymptotically optimal for a family of ergodic sources satisfying Kieffer's condition.
Mohammad DANESH Farid SHEIKHOLESLAM Mehdi KESHMIRI
Consideration of manipulator dynamics and external disturbances in robot control system design can enhance the stability and performance properties of the whole system. In this paper, we present an approach to solve the control problem when the inertia parameters of robot are unknown, and at the same time robot is subjected to external force disturbances. This approach is based on simultaneous estimation of force signal and inertia parameters and utilizing them in the control law. The update laws and the control law are derived based on a single time-varying Lyapunov function, so that the global convergence of the tracking error is ensured. A theorem with a detailed proof is presented to guarantee the global uniform asymptotic stability of the whole system. Some simulations are made for a number of external forces to illustrate the effectiveness of the proposed approach.
Yusuke MATSUOKA Toshimichi SAITO
This paper studies rich superstable phenomena in a nonautonomous piecewise constant circuit including one impulsive switch. Since the vector field of circuit equation is piecewise constant, embedded return map is piecewise linear and can be described explicitly in principle. As parameters vary the map can have infinite extrema with one flat segment. Such maps can cause complicated periodic orbits that are superstable for initial state and are sensitive for parameters. Using a simple test circuit typical phenomena are verified experimentally.
The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the "unpredictability" property of random oracles [12]: If O is a random oracle then it is infeasible to find an input x such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of multi-input CIFEs, where "multi-input" means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform multi-input CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.
Takuji TACHIBANA Hiroaki HARAI
In this paper, we propose an end-to-end lightpath establishment method in multi-domain WDM networks. In this method, each domain contracts the provision of wavelength-state information and the number of wavelengths provided to neighbor domains. According to the contract, each source node selects the probed wavelengths, which are the candidates for backward wavelength reservation. In order to select wavelengths that are likely to be idle through the multi-domain network, the source node collects wavelength-state information from each destination node and ranks wavelengths for each destination node for giving priority. The source node selects the wavelengths with higher ranks. We propose two rank accounting methods for this purpose. Through simulation experiments, we show that the proposed rank accounting methods with the above contract provide better performance in terms of blocking probability with conventional methods, especially when intra-domain traffic is low. We present the effective number of contract wavelengths. Further, we also extend these rank accounting methods to methods that aggressively collect wavelength-state information from other destination nodes. We show further improvement of performance by the extended rank accounting methods.
Hiroki TAMURA Zongmei ZHANG Zheng TANG Masahiro ISHII
An improved algorithm of Guided Local Search called objective function adjustment algorithm is proposed for combinatorial optimization problems. The performance of Guided Local Search is improved by objective function adjustment algorithm using multipliers which can be adjusted during the search process. Moreover, the idea of Tabu Search is introduced into the objective function adjustment algorithm to further improve the performance. The simulation results based on some TSPLIB benchmark problems showed that the objective function adjustment algorithm could find better solutions than Local Search, Guided Local Search and Tabu Search.
Kazuo IWAMA Shuichi MIYAZAKI Kazuya OKAMOTO
An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.
Yoshitaka FUJIWARA Yoshiaki OHNISHI Hideki YOSHIDA
This paper presents a method for tuning the structure of a causal network (CN) to evaluate a learner's profile for a learning assistance system that employs hierarchically structured learning material. The method uses as an initial CN structure causally related inter-node paths that explicitly define the learning material structure. Then, based on this initial structure other inter-node paths (sideway paths) not present in the initial CN structure are inferred by referring to the learner's database generated through the use of a learning assistance system. An evaluation using simulation indicates that the method has an inference probability of about 63% and an inference accuracy of about 30%.
Victor RYZHII Akira SATOU Michael S. SHUR
We study the coupled spatio-temporal variations of the electron density and the electric field (electron plasma oscillations) in high-electron mobility transistors using the developed device model. The excitation of electron plasma oscillations in the terahertz range of frequencies might lead to the emission of terahertz radiation. In the framework of the model developed, we calculate the resonant plasma frequencies and find the conditions for the plasma oscillations self-excitation (plasma instability) We show that the transit-time effect in the high-electric field region near the drain edge of the channel of high-electron mobility transistors can cause the self-excitation of the plasma oscillations. It is shown that the self-excitation of plasma oscillations is possible when the ratio of the electron velocity in the high field region, ud, and the gate length, Lg, i.e., the inverse transit time are sufficiently large in comparison with the electron collision frequency in the gated channel, ν. The transit-time mechanism of plasma instability under consideration can superimpose on the Dyakonov-Shur mechanism predicted previously strongly affecting the conditions of the instability and, hence, terahertz emission. The instability mechanism under consideration might shed light on the origin of terahertz emission from high electron mobility transistors observed in recent experiments.
Yahya Moubarak MEZIANI Jerzy USAKOWSKI Nina DYAKONOVA Wojciech KNAP Dalius SELIUTA Edmundas SIRMULIS Jan DEVENSON Gintaras VALUSIS Frederic BOEUF Thomas SKOTNICKI
Experimental investigations on detection of terahertz radiation are presented. We used plasma wave instability phenomenon in nanometer Silicon field effect transistor. A 30 nm gate length transistor was illuminated by THz radiation at room temperature. We observe a maximum signal near to the threshold voltage. This result clearly demonstrates the possibility of plasma wave THz operation of these nanometer scale devices. The response was attributed to a non resonant detection. We also demonstrate the possibility to observe a resonant detection on the same devices.
Kiyoshi HOSHINO Takanobu TANIMOTO
The hand posture estimation system by searching a similar image from a vast database, such as our previous research, may cause the increase of processing time, and prevent realtime controlling of a robot. In this study, the authors proposed a new estimation method of human hand posture by rearranging a large-scale database with the Self-Organizing Map including self-reproduction and self-annihilation, which enables two-step searches of similar image with short period of processing time, within small errors, and without deviation of search time. The experimental results showed that our system exhibited good performance with high accuracy within processing time above 50 fps for each image input with a 2.8 GHz CPU PC.
Young-Ho YOON Hyung-Gyu LIM Jyung-Hyun LEE Hee-Joon PARK Il-Yong PARK Min-Kyu KIM Chul-Ho WON Byung-Seop SONG Jin-Ho CHO
In this paper, the voice signal processing module has been designed using the micro processor for the use of fully implantable middle ear devices (F-IMEHD). The voice signal processing module for F-IMEHD should be designed to compensate for the hearing loss of hearing impaired person and have the flexibility for compensating various hearing threshold level. So, the voice signal processing module has been designed and implemented to present the various frequency characteristics using the low-power micro processor, MSP430F169. The different voice signal path to the inner ear entrance was considered so that two voice signal would be combined in-phase using an all pass filter with a constant time-delay to improve the vibration of the ossicles.
Takeshi YOSHIDA Yoshihiro MASUI Takayuki MASHIMO Mamoru SASAKI Atsushi IWATA
A low-noise CMOS amplifier operating at a low supply voltage is developed using the two noise reduction techniques of autozeroing and chopper stabilization. The proposed amplifier utilizes a feedback with virtual grounded input-switches and a multiple-output switched op-amp. The low-noise amplifier fabricated in a 0.18-µm CMOS technology achieved 50-nV/
Thang Viet NGUYEN Takehiro MORI Yoshihiro MORI
This paper studies the problem of the relations between existence conditions of common quadratic and those of common infinity-norm Lyapunov functions for sets of discrete-time linear time-invariant (LTI) systems. Based on the equivalence between the robust stability of a class of time-varying systems and the existence of a common infinity-norm Lyapunov function for the corresponding set of LTI systems, the relations are determined. It turns out that although the relation is an equivalent one for single stable systems, the existence condition of common infinity-norm type is strictly implied by that of common quadratic type for the set of systems. Several existence conditions of a common infinity-norm Lyapunov functions are also presented for the purpose of easy checking.
Daisuke TAKEMOTO Shigeaki TAGASHIRA Satoshi FUJITA
In this paper, we propose a new method to enhance the fault-tolerance of the Content Addressable Network (CAN), which is known as a typical pure P2P system based on the notion of Distributed Hash Table (DHT). The basic idea of the proposed method is to introduce redundancy to the management of index information distributed over the nodes in the given P2P network, by allowing each index to be assigned to several nodes, which was restricted to be one in the original CAN system. To keep the consistency among several copies of indices, we propose an efficient synchronization scheme based on the notion of labels assigned to each copy in a distinct manner. The performance of the proposed scheme is evaluated by simulation. The result of simulations indicates that the proposed scheme significantly enhances the fault-tolerance of the CAN system.
Fitri ARNIA Ikue IIZUKA Masaaki FUJIYOSHI Hitoshi KIYA
Two schemes for fast identification of JPEG coded images are proposed in this paper. The aim is to identify the JPEG images that are generated from the same original image and have equivalent or different compression ratios. Fast identification can be achieved since the schemes work on the quantized Discrete Cosine Transform (DCT) domain. It is not required to inverse the quantization and the DCT. Moreover, only a few coefficients are commonly required for identification. The first approach can avoid identification leakage or false negative (FN), and probably result in a few false positives (FP). The second approach can avoid both FN and FP, with a slightly higher processing time. By combining the two schemes, a faster and a more perfect identification can be achieved, in which FN and FP can be avoided.
Il-Yong PARK Hyung-Gyu LIM Young-Ho YOON Min-Kyu KIM Byung-Seop SONG Jin-Ho CHO
In this paper, for the fully-implantable middle ear hearing devices (F-IMEHD), a transcutaneous recharging system that has the function of the bi-directional signal transmission with the implant module in a body as well as recharging battery has been designed and implemented. The electromagnetic coupling method using two coils has been adopted for the transfer of electrical power to recharge internal battery of the implant module. To increase the efficiency of power transfer, the switching frequency of recharging system is determined by the consideration of the resonance of LC tank circuits. The bidirectional signal transmission between the recharging system and the implant module has been designed through the on-off keying modulation of switching signal in the recharging system and the impedance variation of LC tank circuit in the implant module. Through the demonstration of the implemented system, it has been verified that the proposed system has the performance of bidirectional signal transmission with the implant module of F-IMEHDs as well as the battery recharging.
Zhiqiang YOU Tsuyoshi IWAGAKI Michiko INOUE Hideo FUJIWARA
This paper proposes a low power scan test scheme and formulates a problem based on this scheme. In this scheme the flip-flops are grouped into N scan chains. At any time, only one scan chain is active during scan test. Therefore, both average power and peak power are reduced compared with conventional full scan test methodology. This paper also proposes a tabu search-based approach to minimize test application time. In this approach we handle the information during deterministic test efficiently. Experimental results demonstrate that this approach drastically reduces both average power and peak power dissipation at a little longer test application time on various benchmark circuits.
Ayami SUZUKA Ryuhei MIYASHIRO Akiko YOSHISE Tomomi MATSUI
Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.