Pierre-Alain FAYOLLE Benjamin SCHMITT Yuichiro GOTO Alexander PASKO
We present an approach and a web-based system implementation for modeling shapes using real distance functions. The system consists of an applet supporting the HyperFun modeling language. The applet is extended with primitives defined by Euclidean distance from a point to the surface of the shape. Set-theoretic operations (union, intersection, difference) that provide an approximation of the Euclidean distance to a shape built in a constructive way are introduced. Such operations have a controllable error of the exact Euclidean distance to the shape and preserve C1 continuity of the overall function, which is an important condition for further operations and applications. The proposed system should help model various shapes, store them in a concise form, and exchange them easily between different entities on a network. The applet offers also the possibility to export the models defined in the HyperFun language to other formats for raytracing or rapid prototyping.
Atsushi SASAKI Tadashi ARARAGI Shigeru MASUYAMA Keizo MIYATA
We formally define the mobile agent allocation problem from a system-wide viewpoint and then prove that it is strongly NP-complete even if each agent communicates only with two agents. This is the first formal definition for scheduling mobile agents from the viewpoint of load balancing, which enables us to discuss its properties on a rigorous basis. The problem is recognized as preemptive scheduling with independent tasks that require mutual communication. The result implies that almost all subproblems of mobile agent allocation, which require mutual communication of agents, are strongly NP-complete.
Shuji ISOBE Tetsuo KURIYAMA Masahiro MAMBO Hiroki SHIZUYA
The abstract ray-tracing problem asks, for a given scene consisting of a light source, a light receiver and finitely many obstacles in a space, and a given positive integer ε > 0, whether a ray going out from the light source could reach the light receiver with intensity at least ε. The problem is known to be PSPACE-hard, and it is very unlikely that there exists an efficient algorithm to solve the problem without adding any restriction. In this paper, we show that the problem can be solved in polynomial time under some weak practical restrictions.
Yong-Duck CHUNG Young-Shik KANG Jiyoun LIM Sung-Bock KIM Jeha KIM
We proposed a novel structure that improved the linear characteristics of electroabsorption modulator (EAM) with composite quantum-wells as an absorption core layer. We fabricated three types of EAM's whose active cores were 8 nm thick, 12 nm thick and a composite core with 8 nm thick and 12 nm thick quantum-well (QW), respectively. The transfer functions of EAM's were investigated and their third-order inter-modulation distortion (IMD3) was obtained by calculation. The spurious free dynamic range (SFDR) was measured and compared with three types of QW. The linearity of the device with composite quantum-well showed a large enhancement in SFDR by 9.3 dBHz2/3 in TE mode and 7.0 dBHz2/3 in TM mode compared with the conventional EAM.
Moez BELLAMINE Norihiro ABE Kazuaki TANAKA Hirokazu TAKI
It is important to look for alternative forms of physical movement of people and equipments in order to assure diagnosis and maintenance tasks, especially in an environment where workers are subject to danger. An evident and classical solution is the use of the tele-operation and tele-robotics. If the tele-operation helps to solve a lot of real and technical problems, it still remains insufficient to assure an appropriate remote diagnosis and maintenance. The use of virtual reality techniques with the tele-operation can be the solution for an effective remote maintenance and diagnosis. In this paper we show the inefficiency occurred with the use of only tele-operation in the remote maintenance, we introduce our original new system where we use virtual reality techniques and 2D-3D matching (2D camera image-3D virtual objects) with tele-operation to remotely collect machinery vibration data. We explain its structure, implementation and its advantages. We finished by experimenting the system, measuring the different operating times and precision and discuss the results.
Kazuhiko USHIO Hideaki FUJIMOTO
We show that the necessary and sufficient condition for the existence of a balanced C4-bowtie decomposition of the complete multi-graph λKn is λ(n - 1) 0 (mod 16) and n 7. Decomposition algorithms are also given.
Fabien GILIBERT Denis RIDEAU Alexandre DRAY Francois AGUT Michel MINONDO Andre JUGE Pascal MASSON Rachid BOUCHAKOUR
We present measurements of Gate-Induced-Drain-Leak-age at various temperatures and terminal biases. Besides Band-to-Band tunneling leakage observed at high Drain-to-Gate voltage VDG, we also observed Trap-Assisted-Tunneling leakage current at lower VDG. Based on ISE TCAD simulations of the electric field, we propose analytical models for Band-to-Band and Trap-Assisted Gate-Induced-Drain-Leakage currents suitable for compact modeling.
Lih-Shyang CHEN Yuh-Ming CHENG Sheng-Feng WENG Chyi-Her LIN Yong-Kok TAN
In medical education, many of computerized Problem-Based Learning (PBL) systems are used into their training curricula. But these systems do not truly reflect the situations which practitioners may actually encounter in a real medical environment, and hence their effectiveness as learning tools is somewhat limited. Therefore, the present study analyzes the computerized PBL teaching case, and considers how a clinical teaching case can best be presented to the student. Specifically, this paper attempts to develop a web-based PBL system which emulates the real clinical situation by introducing the concept of a "time sequence" within each teaching case. The proposed system has been installed in the medical center of National Cheng Kung University in Taiwan for testing purposes. The participants in this study were 50 of 5th grade (equivalent to 1st grade students in a medical school of the American medical education system) students for the evaluation process. Some experiments are conducted to verify the advantages of designing teaching cases with the concept of the "time sequence."
Nobuo FUNABIKI Jun KAWASHIMA Toru NAKANISHI Kiyohiko OKAYAMA Teruo HIGASHINO
The wavelength-division multiplexing (WDM) technology has been popular in communication societies for providing very large communication bands by multiple lightpaths with different wavelengths on a single optical fiber. Particularly, a double-ring optical network architecture based on the packet-over-WDM technology such as the HORNET architecture, has been extensively studied as a next generation platform for metropolitan area networks (MANs). Each node in this architecture is equipped with a wavelength-fixed optical-drop and a fast tunable transmitter so that a lightpath can be established between any pair of nodes without wavelength conversions. In this paper, we formulate the optical-drop wavelength assignment problem (ODWAP) for efficient wavelength reuse under heterogeneous traffic in this network, and prove the NP-completeness of its decision problem. Then, we propose a simple heuristic algorithm for the basic case of ODWAP. Through extensive simulations, we demonstrate the effectiveness of our approach in reducing waiting times for packet transmissions when a small number of wavelengths are available to retain the network cost for MANs.
An efficient computational Zero-Knowledge Proof of Knowledge whose security relies on the NP-completeness of the Independent Set Problem is presented here. The proposed algorithm is constructed from a bit commitment scheme based on the hardness of the Discrete Logarithm Problem, which guarantees the fulfillment of soundness, completeness and computational zero-knowledge properties, and allows avoiding the use of the Graph Isomorphism Problem, which is present in every known Zero-Knowledge Proofs for the Independent Set Problem.
Takayuki YATO Takahiro SETA Tsuyoshi ITO
Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.
"Can one walk to infinity on Gaussian primes taking steps of bounded length?" We adopted computational techniques to probe into this open problem. We propose an efficient method to search for the farthest point reachable from the origin, which can be parallelized easily, and have confirmed the existence of a moat of width k =, whereas the best previous result was k = due to Gethner et al. The amount of computation needed for k = is about 5000 times larger than that for k =. A refinement of Vardi's estimate for the farthest distance reachable from the origin is proposed. The proposed estimate incorporates discreteness into Vardi's that is based on percolation theory.
EunSeo CHOI Jihoon NA Gopinath MUDHANA Seon Young RYU Byeong Ha LEE
We implemented all-fiber delay line using linearly chirped fiber Bragg gratings (CFBG), which can be applicable for reflectometry or optical coherence tomography (OCT). Compared with the previously reported delay lines, the proposed fiber-based optical delay line has in principle novel advantages such as automatic dispersion cancellations without additional treatment and a gain in optical delay that is dependent on parameters of used CFBGs. Dispersion compensation in optical delay line (ODL), which is the indispensable problem in bulk optics based ODL, is demonstrated in fiber by using two identical but reversely ordered CFBGs. Amplified variable optical delay of around 2.5 mm can be obtained by applying small physical stretching of one of CFBGs in the proposed scheme. The operational principles of the all-fiber variable optical delay line, which are based on the distributed reflection characteristic of a CFBG employed, are described. Especially properties such as in-line automatic dispersion cancellation and amplified optical delay under strain are dealt. To demonstrate the properties of the proposed scheme, which is theoretical consequences under assumptions, an all-fiber optical delay line have been implemented using fiber optic components such as fiber couplers and fiber circulators. With the implanted ODL, the group delay and amplified optical delay length was measured with/without strain. The wavelength independent group delay measured within reflection bandwidth of the CFBG has proved the property of automatic dispersion cancellations in the proposed fiber delay line. Optical delay length of 2.5 mm was obtained when we apply small physical stretching to the CFBG by 100 µm and this is expressed by the amplification factor of 25. Amplification factor 25, which is less than theoretical value of 34 due to slipping of fiber in the fiber holder, shows that the proposed scheme can provide large optical delay with applying small physical stretching to the CFBG. We measure slide glass thickness to check the performance of the fiber delay line and the good agreement in measured and physical thickness of slide glass (1 mm thick) validates the potential of proposed delay line in the applications of optical reflectometry and OCT. We also discuss the problem and the solution to improve the performance.
This paper provides an overview of research in channel modeling for multiple-input multiple-output (MIMO) data transmission focusing on a radio wave propagation. A MIMO channel is expressed as an equivalent circuit with a limited number of eigenpaths according to the singular-value decomposition (SVD). Each eigenpath amplitude depends on the propagation structure not only of the path direction profiles for both transmission and reception points but also of intermediate regions. Inherent in adaptive control is the problem of instability as a hidden difficulty. In this paper these issues are addressed and research topics on MIMO from a radio wave propagation viewpoint are identified.
The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of the communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required for each packet. In this paper, we derive lower bounds for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of priorities 1 and α 1: 1 + /α ln if α α*; 1/(1 - e-τ0) if 1 α < α*, where α* 1.657 and τ0 is a root of the equality that e-τ(1/α + τ)=1 - e-τ. As an immediate result, this shows a lower bound 1.466 for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of single priority, which slightly improves the best known lower bound 1.366.
The rapid growth of multimedia applications has increased interest in the compression of video data. This paper presents a new method for improving the compression ratio of video data, which can be easily used in a multilayer environment for error resilience applications as well. Data of four luminance blocks in a macroblock are processed and arranged in such a way that important macroblock data is compressed in one block(A), while the rest of the three remaining data blocks(H,V,D) are given difference values in the horizontal, vertical and diagonal directions. This results in a reduced bitstream size because of the low-valued data present in the three blocks(H,V,D), giving better compression at low bitrates. In an error resilient environment, the important data block in a macroblock is transmitted in a secure channel while the remaining three blocks with difference data are sent via a lossy channel. If error occurs in the lossy channel, picture can still be reconstructed with reasonably good quality using only the block data that is transmitted in the secure channel.
Ming-Ta YANG Yo-Jen WANG Patricia Pei-Chen HO Tzu-Jin YEH Darryl Chih-Wei KUO Chin-Wei KUO
The new design with minimum loop inductance suitable for the measurements at high frequencies with substrate bias is described. These test structures allow characterizing 4-terminal MOSFETs with a standard two-port Network Analyzer. The high-frequency behavior of bulk effect in MOSFETs is studied at different bias conditions for a 0.18 µm RF CMOS technology. The BSIM3 extension RF MOSFET modeling with bulk effect is verified and analyzed from two-port Y-parameter results. The result of RF NMOSFET shows that a good accuracy of the 4-terminal RF MOSFET modeling is achieved.
Dimitrios VOUDOURIS Stergios STERGIOU George PAPAKONSTANTINOU
In this paper two algorithms for the synthesis and minimization of a CA (cellular array architecture) are proposed. Starting from a completely specified single-output switching function, our methods produce rectangularly shaped arrays of cells, interconnected in chains, with an effort to minimize the number of the produced chains (cascades). This kind of cellular topology is known throughout the bibliography as Maitra cellular arrays. The significance of those algorithms is underlined by the fact that this particular type of cellular architecture can be mapped to reversible circuits and gates (generalized Toffoli gates), which are the type of logic used in quantum circuits. The proposed methodologies include use of ETDDs (EXOR ternary decision diagrams), and switching function decompositions (including new types of boolean expansions).
This paper newly proposes a method to automatically decompose real scene images into multiple object-oriented component regions. First, histogram patterns of a specific image feature, such as intensity or hue value, are estimated from image sequence and stored up. Next, Gaussian distribution parameters which correspond to object components involved in the scene are estimated by applying the EM algorithm to the accumulated histogram. The number of the components is simultaneously estimated by evaluating the minimum value of Bayesian Information Criterion (BIC). This method can be applied to a variety of computer vision issues, for example, the color image segmentation and the recognition of scene situation transition. Experimental results applied for indoor and outdoor scenes showed the effectiveness of the proposed method.
Koji GODA Toshinori YAMADA Shuichi UENO
This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.