RHiNET-2/SW: a high-throughput, compact network-switch using 8.8-gbit/s optical interconnection

We have developed a high-throughput, compact network switch (the RHiNET-2/SW) for a distributed parallel computing system. Eight pairs of 800-Mbit/s×12-channel optical interconnection modules and a CMOS ASIC switch are integrated on a compact circuit board. To realize high-throughput (64 Gbit/s) and low-latency network, the SW-LSI has a customized high-speed LVDS I/O interface, and a high-speed internal SRAM memory in a 784-pin BGA one-chip package. We have also developed device implementation technologies to overcome the electrical problems (loss and crosstalk) caused by such high integration. The RHiNET-2/SW system enables high-performance parallel processing in a distributed computing environment. Shinji Nishimura: He is a researcher in the Department of Network System at the Central Research Laboratory, Hitachi Ltd., at Tokyo. He obtained his bachelors degree in Electronics Engineering from the University of Tokyo in 1989, and his M.E. from the University of Tokyo in 1991. He joined a member of the Optical Interconnection Hitachi Laboratory from 1992. His research interests are in hardware technology for the optical interconnection technologies in the computer and communication systems. Katsuyoshi Harasawa: He is a Senior Enginner of Hitachi Communication Systems Inc. He obtained his bachelors degree in Electrical Engineering from Tokyo Denki University. He is a chief of development of the devices and systems for the optical telecommunication. He was engaged in Development of Optical Reciever and Transmitter module. He joined RWCP project from 1997. His research interests are in hardward technology for optical interconnection in distributed parallel computing system (RHiNET). Nobuhiro Matsudaira: He is a engineer in the Hitachi Communication Systems, Inc. He obtained his bachelors degree in Mercantile Marine Engineering from the Kobe University of Mercantile Marine in 1986. He was engaged in Development of Optical Reciever and Transmitter module at 2.4 Gbit/s to 10Gbit/s. He joined RWCP project from 1998. His reserch interests are in hardware technology for the optical interconnection technology in the computer and communication systems. Shigeto Akutsu: He is a staff in Hitachi Communication Systems Inc. He obtained his bachelors degree in Electronics from Kanagawa University, Japan in 1998. His research interests are hardware technology for the optical interconnection technology in the computer and communication systems. Tomohiro Kudoh, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1992. He has been chief of the parallel and distributed architecture laboratory, Real World Computing Partnership since 1997. His research interests include the area of parallel processing and network for high performance computing. Hiroaki Nishi: He received B.E., M.E. from Keio University, Japan, in 1994, 1996, respectively. He joined Parallel & Distributed Architecture Laboratory, Real World Computing Partnership in 1999. He is currently working on his Ph.D. His research interests include area of interconnection networks. Hideharu Amano, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1986. He is now an Associate Professor in the Department of Information and Computer Science, Keio University. His research interests include the area of parallel processing and reconfigurable computing.     

A method of model improvement for spotting recognition of gestures using an image sequence

We have developed a real-time gesture recognition system whose models can be taught by only one instruction. Therefore the system can adapt to new gesture performer quickly but it can not raise the recognition rates even if we teach gestures many times. That is because the system could not utilize all the teaching data. In order to cope with the problem, averages of teaching data are calculated. First, the best frame correspondence of the teaching data and the model is obtained by Continuous DP. Next the averages and variations are calculated for each frame of the model. We show the effectiveness of our method in the experiments. Takuichi Nishimura: He is a researcher of Multi-modal Function Tsukuba Laboratory and Information Basis Function Laboratory at the Real World Computing Partnership. He has engaged in motion image understanding, multi-modal human computer interface, multi-modal information retrieval, and mobile robot navigation. He completed the master’s course of the University of Tokyo in 1992. Hiroaki Yabe: He is from SHARP corporation working as a researcher of Multi-modal Function Tsukuba Laboratory and Information Basis Function Tsukuba Laboratory at the Real World Computing Partnership. He has engaged in motion image understanding, multi-modal human computer interface, multi-modal information retrieval. He completed the master’s course of the University of Tokyo in 1995. Ryuichi Oka, Ph.D.: He is a chief of Multi-modal Function Tsukuba Laboratory and Information Basis Function Laboratory at Tsukuba Research Center of the Real World Computing Partnership (RWC Japan) which started in 1992. His research interests include motion image understanding, spontaneous speech understanding, self-organisation information base, multi-modal human computer interface, multi-modal information retrieval, mobile robot, integration of symbol and pattern, and super parallel computation. He received his Ph.D degree in Engineering from the University of Tokyo.     

An algorithm for similar utterance section extraction for managing spoken documents

This paper proposes a new, efficient algorithm for extracting similar sections between two time sequence data sets. The algorithm, called Relay Continuous Dynamic Programming (Relay CDP), realizes fast matching between arbitrary sections in the reference pattern and the input pattern and enables the extraction of similar sections in a frame synchronous manner. In addition, Relay CDP is extended to two types of applications that handle spoken documents. The first application is the extraction of repeated utterances in a presentation or a news speech because repeated utterances are assumed to be important parts of the speech. These repeated utterances can be regarded as labels for information retrieval. The second application is flexible spoken document retrieval. A phonetic model is introduced to cope with the speech of different speakers. The new algorithm allows a user to query by natural utterance and searches spoken documents for any partial matches to the query utterance. We present herein a detailed explanation of Relay CDP and the experimental results for the extraction of similar sections and report results for two applications using Relay CDP. Yoshiaki Itoh has been an associate professor in the Faculty of Software and Information Science at Iwate Prefectural University, Iwate, Japan, since 2001. He received the B.E. degree, M.E. degree, and Dr. Eng. from Tokyo University, Tokyo, in 1987, 1989, and 1999, respectively. From 1989 to 2001 he was a researcher and a staff member of Kawasaki Steel Corporation, Tokyo and Okayama. From 1992 to 1994 he transferred as a researcher to Real World Computing Partnership, Tsukuba, Japan. Dr. Itoh's research interests include spoken document processing without recognition, audio and video retrieval, and real-time human communication systems. He is a member of ISCA, Acoustical Society of Japan, Institute of Electronics, Information and Communication Engineers, Information Processing Society of Japan, and Japan Society of Artificial Intelligence. Kazuyo Tanaka has been a professor at the University of Tsukuba, Tsukuba, Japan, since 2002. He received the B.E. degree from Yokohama National University, Yokohama, Japan, in 1970, and the Dr. Eng. degree from Tohoku University, Sendai, Japan, in 1984. From 1971 to 2002 he was research officer of Electrotechnical Laboratory (ETL), Tsukuba, Japan, and the National Institute of Advanced Science and Technology (AIST), Tsukuba, Japan, where he was working on speech analysis, synthesis, recognition, and understanding, and also served as chief of the speech processing section. His current interests include digital signal processing, spoken document processing, and human information processing. He is a member of IEEE, ISCA, Acoustical Society of Japan, Institute of Electronics, Information and Communication Engineers, and Japan Society of Artificial Intelligence. Shi-Wook Lee received the B.E. degree and M.E. degree from Yeungnam University, Korea and Ph.D. degree from the University of Tokyo in 1995, 1997, and 2001, respectively. Since 2001 he has been working in the Research Group of Speech and Auditory Signal Processing, the National Institute of Advanced Science and Technology (AIST), Tsukuba, Japan, as a postdoctoral fellow. His research interests include spoken document processing, speech recognition, and understanding.     

Public opinion channel for communities in the information age

In this paper, we propose as a new challenge a public opinion channel which can provide a novel communication medium for sharing and exchanging opinions in a community. Rather than simply developing a means of investigating public opinion, we aim at an active medium that can facilitate mutual understanding, discussion, and public opinion formation. First, we elaborate the idea of public opinion channels and identify key issues. Second, we describe our first step towards the goal using the talking virtualized egos metaphor. Finally, we discuss a research agenda towards the goal. Toyoaki Nishida, Dr.Eng.: He is a professor of Department of Information and Communication Engineering, School of Engineering, The University of Tokyo. He received the B.E., the M.E., and the Doctor of Engineering degrees from Kyoto University in 1977, 1979, and 1984 respectively. His research centers on artificial intelligence in general. His current research focuses on community computing and support systems, including knowledge sharing, knowledge media, and agent technology. He has been leading the Breakthrough 21 Nishida Project, sponsored by Ministry of Posts and Telecommunications, Japan, aiming at understanding and assisting networked communities. Since 1997, he is a trustee for JSAI (Japanese Society for Artificial Intelligence), and serves as the program chair of 1999 JSAI Annual Convention. He is an area editor (intelligent systems) of New Generation Computing and an editor of Autonomous Agents and Multiagent Systems. Nobuhiko Fujihara, Ph.D.: He is a fellow of Breakthrough 21 Nishida project, Communications Research Laboratory sponsored by Ministry of Posts and Telecommunications, Japan. He received the B.E., the M.E., and the Ph.D. in Human Sciences degrees from Osaka University in 1992, 1994, and 1998 respectively. He has a cognitive psychological background. His current research focuses on: (1) cognitive psychological analysis of human behavior in a networked community, (2) investigation of information comprehension process, (3) assessment and proposition of communication tools in networking society. Shintaro Azechi: He is a fellow of Breakthrough 21 Nishida project, Communications Research Laboratory sponsored by Ministry of Posts and Telecommunications, Japan. He received the B.E. and the M.E. of Human Sciences degrees from Osaka University in 1994 and 1996 respectively. He is a Doctoral Candidate of Graduate School of Human Sciences, Osaka University. His current researches focus on (1) human behavior in networking community (2) social infomation process in human mind (3) development of acessment technique for communication tools in networkingsociety. His approach is from social psychological view. Kaoru Sumi, Dr.Eng.: She is a Researcher of Breakthrough 21 Nishida Project. She received her Bachelor of Science at School of Physics, Science University of Tokyo. She received her Master of Systems Management at Graduate School of Systems Management, The university of Tsukuba. She received her Doctor of engineering at Graduate School of Engineering, The University of Tokyo. Her research interests include knowledge-based systems, creativity supporting systems, and their applications for facilitating human collaboration. She is a member of the Information Processing Society of Japan (IPSJ), the Japanese Society for Artificial Intelligence (JSAI). Hiroyuki Yano, Dr.Eng.: He is a senior research official of Kansai Advanced Research Center, Communications Research Laboratory, Ministry of Posts and Telecommunications. He received the B.E., the M.E., and the Doctor of Engineering degrees from Tohoku University in 1986, 1988, and 1993 respectively. His interests of research include cognitive mechanism of human communications. His current research focuses on discourse structure, human interface, and dialogue systems for human natural dialogues. He is a member of the Japanese Society for Artificial Intelligence, the Association for Natural Language Processing, and the Japanese Cognitive Science Society. Takashi Hirata: He is a doctor course student in Graduate School of Information Scienc at Nara Institute of Science and Technology (NAIST). He received a master of engineering from NAIST in 1998. His research interest is knowledge media and knowledge sharing. He is a member of Information Processing Society of Japan (IPSJ), Japan Association for Artificial Intelligence (JSAI) and The Institute of Systems, Control and Information Engineers (ISCIE).     

User-independent gesture recognition by relative-motion extraction and discriminant analysis

We propose a new method for user-independent gesture recognition from time-varying images. The method uses relative-motion extraction and discriminant analysis for providing online learning/recognition abilities. Efficient and robust extraction of motion information is achieved. The method is computationally inexpensive which allows real-time operation on a personal computer. The performance of the proposed method has been tested with several data sets and good generalization abilities have been observed: it is robust to changes in background and illumination conditions, to users’ external appearance and changes in spatial location, and successfully copes with the non-uniformity of the performance speed of the gestures. No manual segmentation of any kind, or use of markers, etc. is necessary. Having the above-mentioned features, the method could be successfully used as a part of more refined human-computer interfaces. Bisser R. Raytchev: He received his BS and MS degrees in electronics from Tokai University, Japan, in 1995 and 1997 respectively. He is currently a doctoral student in electronics and information sciences at Tsukuba University, Japan. His research interests include biological and computer vision, pattern recognition and neural networks. Osamu Hasegawa, Ph.D.: He received the B.E. and M.E. degrees in Mechanical Engineering from the Science University of Tokyo, in 1988, 1990 respectively. He received Ph.D. degree in Electrical Engineering from the University of Tokyo, in 1993. Currently, he is a senior research scientist at the Electrotechnical Laboratory (ETL), Tsukuba, Japan. His research interests include Computer Vision and Multi-modal Human Interface. Dr. Hasegawa is a member of the AAAI, the Institute of Electronics, Information and Communication Engineers, Japan (IEICE), Information Processing Society of Japan and others. Nobuyuki Otsu, Ph.D.: He received B.S., Mr. Eng. and Dr. Eng. in Mathematical Engineering from the University of Tokyo in 1969, 1971, and 1981, respectively. Since he joined ETL in 1971, he has been engaged in theoretical research on pattern recognition, multivariate data analysis, and applications to image recognition in particular. After taking positions of Head of Mathematical Informatics Section (since 1985) and ETL Chief Senior Scientist (since 1990), he is currently Director of Machine Understanding Division since 1991, and concurrently a professor of the post graduate school of Tsukuba University since 1992. He has been involved in the Real World Computing program and directing the R&D of the project as Head of Real World Intelligence Center at ETL. Dr. Otsu is members of Behaviormetric Society and IEICE of Japan, etc.     

Toward a real-world knowledge medium: Building a guidance system for exhibition tours

We propose a notion of a real-world knowledge medium by presenting our ongoing project to build a guidance system for exhibition tours. In order to realize a knowledge medium usable in the real world, we focus on the context-awareness of users and their environments. Our system is a personal mobile assistant that provides visitors touring exhibitions with information based on their spatial/temporal locations and individual interests. We also describe an application of knowledge sharing used in the actual exhibition spaces. Yasuyuki Sumi, Ph.D.: He has been a researcher at ATR Media Integration & Communications Research Laboratories since 1995. His research interests include knowledge-based systems, creativity supporting systems, and their applications for facilitating human collaboration. He received his B. Eng. degree from Waseda University in 1990, and M. Eng. and D. Eng. degrees in information engineering from the University of Tokyo in 1992 and 1995, respectively. He is a member of Institutes of Electronics, Information and Communication Engineers (IEICE) of Japan, the Information Processing Society of Japan (IPSJ), the Japanese Society for Artificial Intelligence (JSAI), and American Association for Artificial Intelligence (AAAI). Kenji Mase, Ph.D.: He received the B.S. degree in Electrical Engineering and the M.S. and Ph.D. degrees in Information Engineering from Nagoya University in 1979, 1981 and 1992 respectively. He has been with ATR (Advanced Telecommunications Research Institute) Media Integration & Communications Research Laboratories since 1995 and is currently the head of Department 2. He joined the Nippon Telegraph and Telephone Corporation (NTT) in 1981 and had been with the NTT Human Interface Laboratories. He was a visiting researcher at the Media Laboratory, MIT in 1988–1989. His research interests include image sequence processing of human actions, computer graphics, computer vision, artificial intelligence and their applications for computer-aided communications and human-machine interfaces. He is a member of the Information Processing Society of Japan (IPSJ), Institutes of Electronics, Information and Communication Engineers (IEICE) of Japan and IEEE Computer Society.     

A simple generational real-time garbage collection scheme

This paper presents and empirically evaluates a generational real-time garbage collection scheme, which is based on combining Baker’s real-time scheme with a simple generational scheme by Andrew W. Appel. Real World Computing Partnership. Khayri A. M. Ali, Ph.D.: He currently works as Dean of the Faculty of Computer Science at October University for Modern Sciences and Arts, Egypt. He received his B. Sc. (1970) in Electronics, his M. Sc. (1977) in Automatic Control, both from Egypt. He received his Ph.D. in Computer Systems from the Royal Institute of Technology, Stockholm, in 1984. His research interests are in developing parallel and distributed logic, functional, object-oriented, and constraints programming systems.     

AgentTeamwork: Coordinating grid-computing jobs with mobile agents

AgentTeamwork is a grid-computing middleware system that dispatches a collection of mobile agents to coordinate a user job over remote computing nodes in a decentralized manner. Its utmost focus is to maintain high availability and dynamic balancing of distributed computing resources to a parallel-computing job. For this purpose, a mobile agent is assigned to each process engaged in the same job, monitors its execution at a different machine, takes its periodical execution snapshot, moves it to a lighter-loaded machine, and resumes it from the latest snapshot upon an accidental crash. The system also restores broken inter-process communication involved in the same job using its error-recoverable socket and mpiJava libraries in collaboration among mobile agents. We have implemented the first version of our middleware including a mobile agent execution platform, error-recoverable socket and mpiJava API libraries, a job wrapper program, and several types of mobile agents such as commander, resource, sentinel, and bookkeeper agents, each orchestrating, allocating resources to, monitoring and maintaining snapshots of a user process respectively. This paper presents AgentTeamwork’s execution model, its implementation techniques, and our performance evaluation using the Java Grande benchmark test programs. Munehiro Fukuda received a B.S. from the College of Information Sciences and an M.S. from the Master’s Program in Science and Enginnering at the University of Tsukuba in 1986 and 1988. He received his M.S. and Ph.D. in Information and Computer Science at the University of California at Irvine in 1995 and 1997, respectively. He worked at IBM Tokyo Research Laboratory from 1988 to 1993 and taught at the University of Tsukuba from 1998 to 2001. Since 2001, he has been an assistant professor at Computing & Software Systems, the University of Washington, Bothell. His research interests include mobile agents, multi-threading, cluster computing, grid computing and distributed simulations. Koichi Kashiwagi received a Bachelor of Science degree from the Faculty of Science, Ehime University in 2000 and a Master of Engineering degree from the Department of Compter Science, Ehime University in 2002. In 2004 he became a research assistant in Department of Compter Science, Ehime University. His research interests include distributed computing, job scheduling, and grid computing. Shin-ya Kobayashi received the B.E. degree, M.E. degree, and Dr.E. degree in Communication Engineering from Osaka University in 1985, 1988, and 1991 respectively. From 1991 to 1999, he was on the faculty of Engineering at Kanazawa University, Japan. From 1999 to 2004, He was an Associate Professor in the Department of Computer Science, Ehime University. He is a Professor at Graduate School of Science and Engineering, Ehime University. His research interests include distributed processing, and parallel processing. He is a member of the Information Processing Society of Japan, the Institute of Electrical Engineers of Japan, IEEE, and ACM.     

Algebraic retrieval of fragmentarily indexed video

When dealing with long video data, the task of identifying and indexing all meaningful subintervals that become answers to some queries is infeasible. It is infeasible not only when done by hand but even when done by using latest automatic video indexing techniques. Whether manually or automatically, it is only fragmentary video intervals that we can identify in advance of any database usage. Our goal is to develop a framework for retrieving meaningful intervals from such fragmentarily indexed video data. We propose a set of algebraic operations that includes ourglue join operations, with which we can dynamically synthesize all the intervals that are conceivably relevant to a given query. In most cases, since these operations also produce irrelevant intervals, we also define variousselection operations that are useful in excluding them from the answer set. We also show the algebraic properties possessed by those operations, which establish the basis of an algebraic query optimization. Katsumi Tanaka, D. Eng.: He received his B.E., M.E., and D.Eng. degrees in information science from Kyoto University, in 1974, 1976, and 1981, respectively. Since 1994, he is a professor of the Department of Computer and Systems Engineering and since 1997, he is a professor of the Division of Information and Media Sciences, Graduate School of Science and Technology, Kobe University. His research interests include object-oriented, multimedia and historical databases abd multimedia information systems. He is a member of the ACM, IEEE Computer Society and the Information Processing Society of Japan. Keishi Tajima, D.Sci.: He received his B.S, M.S., and D.S. from the department of information science of University of Tokyo in 1991, 1993, and 1996 respectively. Since 1996, he is a Research Associate in the Department of Computer and Systems Engineering at Kobe University. His research interests include data models for non-traditional database systems and their query languages. He is a member of ACM, ACM SIGMOD, Information Processing Society of Japan (IPSJ), and Japan Society for Software Science and Technology (JSSST). Takashi Sogo, M.Eng.: He received B.E. and M.E. from the Department of Computer and Systems Engineering, Kobe University in 1998 and 2000, respectively. Currently, he is with USAC Systems Co. His research interests include video database systems. Sujeet Pradhan, D.Eng.: He received his BE in Mechanical Engineering from the University of Rajasthan, India in 1988, MS in Instrumentation Engineering in 1995 and Ph.D. in Intelligence Science in 1999 from Kobe University, Japan. Since 1999 May, he is a lecturer of the Department of Computer Science and Mathematics at Kurashiki University of Science and the Arts, Japan. A JSPS (Japan Society for the Promotion of Science) Research Fellow during the period between 1997 and 1999, his research interests include video databases, multimedia authoring, prototypebased languages and semi-structured databases. Dr. Pradhan is a member of Information Processing Society of Japan.     

A separation method for DNA computing based on concentration control

A separation method for DNA computing based on concentration control is presented. The concentration control method was earlier developed and has enabled us to use DNA concentrations as input data and as filters to extract target DNA. We have also applied the method to the shortest path problems, and have shown the potential of concentration control to solve large-scale combinatorial optimization problems. However, it is still quite difficult to separate different DNA with the same length and to quantify individual DNA concentrations. To overcome these difficulties, we use DGGE and CDGE in this paper. We demonstrate that the proposed method enables us to separate different DNA with the same length efficiently, and we actually solve an instance of the shortest path problems. Masahito Yamamoto, Ph.D.: He is associate professor of information engineering at Hokkaido University. He received Ph.D. from the Graduate School of Engineering, Hokkaido University in 1996. His current research interests include DNA computing based the laboratory experiments. He is a member of Operations Research Society of Japan, Japanese Society for Artificial Intelligence, Information Processing Society of Japan etc. Atsushi Kameda, Ph.D.: He is the research staff of Japan Science and Technology Corporation, and has participated in research of DNA computing in Hokkaido University. He received his Ph.D. from Hokkaido University in 2001. For each degree he majored in molecular biology. His research theme is about the role of polyphosphate in the living body. As one of the researches relevant to it, he constructed the ATP regeneration system using two enzyme which makes polyphosphate the phosphagen. Nobuo Matsuura: He is a master course student of Division of Systems and Information Engineering of Hokkaido University. His research interests relate to DNA computing with concentration control for shortest path problems, as a means of solution of optimization problems with bimolecular. Toshikazu Shiba, Ph.D.: He is associate, professor of biochemical engineering at Hokkaido University. He received his Ph.D. from Osaka University in 1991. He majored in molecular genetics and biochemistry. His research has progressed from bacterial molecular biology (regulation of gene expression of bacterial cells) to tissue engineering (bone regeneration). Recently, he is very interested in molecular computation and trying to apply his biochemical idea to information technology. Yumi Kawazoe: She is a master course student of Division of Molecular Chemistry of Hokkaido University. Although her major is molecular biology, she is very interested in molecular computation and bioinformatics. Azuma Ohuchi, Ph.D.: He is professor of Information Engineering at the University of Hokkaido, Sapporo, Japan. He has been developing a new field of complex systems engineering, i.e., Harmonious Systems Engineering since 1995. He has published numerous papers on systems engineering, operations research, and computer science. In addition, he is currently supervising projects on DNA computing, multi-agents based artificial market systems, medical informatics, and autonomous flying objects. He was awarded “The 30th Anniversary Award for Excellent Papers” by the Information Processing Society of Japan. He is a member of Operations Research Society of Japan, Japanese Society for Artificial Intelligence, Information Processing Society of Japan, Japan Association for Medical Informatics, IEEE Computer Society, IEEE System, Man and Cybernetics Society etc. He received PhD from Hokkaido University in 1976.     

Improving cache attacks by considering cipher structure

A concrete attack using side channel information from cache memory behaviour was proposed for the first time at ISITA 2002. The attack uses the difference between execution times associated with S-box cache-hits and cache-misses to recover the intermediate key. Recently, a theoretical estimation of the number of messages needed for the attack was proposed and it was reported that the average method obtains key information with fewer messages than maximum threshold or intermediate threshold method. Taking the structure of cipher into account, this paper provided the cache attack in which the average method is embodied, and provides improved key estimation. This paper includes the study on the attack that exploits internal collision. Yukiyasu Tsunoo received his BE degree from Waseda University in 1982, MS degree from JAIST, Dr.Eng from Chuo University. He joined NEC Software Hokuriku, Ltd. in 1985. He is now a research fellow of NEC Internet Systems Research Laboratories. He is engaged in the designing of common key ciphers and the study of evaluation technique. Dr. Tsunoo is a member of the Expert Commission of Information Security Research, The Institute of Electronics, Information and Communication Engineers, the Information Processing Society of Japan, the Japan Society for Security Management and the Atomic Energy Society of Japan. Etsuko Tsujihara received her BS degree from Aoyama Gakuin University in 1983. She joined NEC in 1983. She developed the VLSI automatic layout system. She joined NEC Software Hokuriku Ltd. in 1986 and Y.D.K. Co. Ltd. in 2004. She is engaged in the designing of common key ciphers and the study of evaluation technique. Maki Shigeri received her BE degree from University of Tsukuba in 1992. She joined NEC Software Hokuriku Ltd. in 1992. She is engaged in the designing of common key ciphers and the study of evaluation technique. Hiroyasu Kubo received his BE degree from Kanazawa Institute of Technology in 1990. He joined NEC Software Hokuriku Ltd. in 1990. He is engaged in the designing of common key ciphers and the study of evaluation technique. Kazuhiko Minematsu received his BS degree from Waseda University in 1996, MS degree in 1998 and joined NEC in 1998. He is engaged in the designing of common key ciphers and research on block cipher modes of operations. He is a member of the Information Processing Society of Japan, the Society of Information Theory and Its Applications.     

Edge detection with reaction-diffusion equations having a local average threshold

The present paper proposes an edge detection algorithm with the FitzHugh-Nagumo reaction-diffusion equations. The authors previously found that the discretized version of the reaction-diffusion equations organizes a static pulse at an edge position for a binary image or for a binarized image with a fixed threshold level. By finding static pulses from the result of the discretized version, we can detect edges. The algorithm proposed here furthermore detects edges from a gray-scale image. In order to handle the gray-scale image, the proposed algorithm computes a local average level of image brightness distribution with a simple diffusion equation and simultaneously utilizes the average level as the threshold level of the reaction-diffusion equations. That is, the local average level obtained by the simple diffusion equation modulates the threshold level of the reaction-diffusion equations. The proposed set of the reaction-diffusion equations coupled with the simple diffusion equation causes a pulse at a true edge position and also a pseudopulse at a pseudoposition. Thus, we additionally propose an algorithm that eliminates the pseudopulse and extracts the true one. We apply the proposed algorithm and a previous representative algorithm to well-known test images for confirming the validity of the proposed algorithm. The text was submitted by the authors in English. Atsushi Nomura, born in 1966, obtained his Doctor of Engineering degree from Yamaguchi University, Japan, in 1994. Since 2001 he has been an associate professor of Faculty of Education at the university. His fields of research are image processing and computer vision. He is an author or coauthor of two book chapters and 13 research papers. He is a member of the Information Processing Society of Japan; the Physical Society of Japan; the Institute of Electronics, Information, and Communication Engineers; and the Optical Society of America. Makoto Ichikawa, born in 1965, obtained his Ph.D. degree from Osaka City University, Japan, in 1994. He was a post-doctoral fellow at Centre for Vision Research, York University, Canada. In 1998, he joined Faculty of Engineering, Yamaguchi University, Japan. Since 2006 he has been an associate professor of the Department of Psychology, Faculty of Letters, Chiba University, Japan. His fields of research are spatiotemporal aspects of perception, and integration processing in perception and cognition. He is the author or coauthor of five books and 20 research papers. He is a member of the Japan Society of KANSEI Engineering, the Japanese Psychological Association, Vision Society of Japan, and Vision Sciences Society. Rismon Hasiholan Sianipar, born in 1977, obtained his Master of Engineering degree from Mataram University, Indonesia, in 2002. In 2004, he entered Yamaguchi University as a research associate. He is currently a Ph.D. candidate in the Graduate School of Science and Engineering, Yamaguchi University, Japan. He is the coauthor of one book chapter and 2 research papers. His fields of research are signal and image processing. Hidetoshi Miike, born in 1948, obtained his Doctor of Engineering degree from Kyushu University, Japan in 1976. In 1976, he joined Faculty of Engineering, Yamaguchi University. Since 1991, he has been a professor of the university. His research interests include nonlinear sciences and fluid dynamics. He is a coauthor of 5 books and more than 100 research papers. He is a member of the Information Processing Society of Japan, the Physical Society of Japan, IEEE Computer Society, and the American Association for the Advancement of Science.     

Design and analysis of the Dual-Torus Network

In this paper, we propose a new topology called theDual Torus Network (DTN) which is constructed by adding interleaved edges to a torus. The DTN has many advantages over meshes and tori such as better extendibility, smaller diameter, higher bisection width, and robust link connectivity. The most important property of the DTN is that it can be partitioned into sub-tori of different sizes. This is not possible for mesh and torus-based systems. The DTN is investigated with respect to allocation, embedding, and fault-tolerant embedding. It is shown that the sub-torus allocation problem in the DTN reduces to the sub-mesh allocation problem in the torus. With respect to embedding, it is shown that a topology that can be embedded into a mesh with dilation δ can also be embedded into the DTN with less dilation. In fault-tolerant embedding, a fault-tolerant embedding method based on rotation, column insertion, and column skip is proposed. This method can embed any rectangular grid into its optimal square DTN when the number of faulty nodes is fewer than the number of unused nodes. In conclusion, the DTN is a scalable topology well-suited for massively parallel computation. Sang-Ho Chae, M.S.: He received the B.S. in the Computer Science and Engineering from the Pohang University of Science and Technology (POSTECH) in 1994, and the M.E. in 1996. Since 1996, he works as an Associate Research Engineer in the Central R&D Center of the SK Telecom Co. Ltd. He took part in developing SK Telecom Short Message Server whose subscribers are now over 3.5 million and Advanced Paging System in which he designed and implemented high availability concepts. His research interests are the Fault Tolerance, Parallel Processing, and Parallel Topolgies. Jong Kim, Ph.D.: He received the B.S. degree in Electronic Engineering from Hanyang University, Seoul, Korea, in 1981, the M.S. degree in Computer Science from the Korea Advanced Institute of Science and Technology, Seoul, Korea, in 1983, and the Ph.D. degree in Computer Engineering from Pennsylvania State University, U.S.A., in 1991. He is currently an Associate Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. Prior to this appointment, he was a research fellow in the Real-Time Computing Laboratory of the Department of Electrical Engineering and Computer Science at the University of Michigan from 1991 to 1992. From 1983 to 1986, he was a System Engineer in the Korea Securities Computer Corporation, Seoul, Korea. His major areas of interest are Fault-Tolerant Computing, Performance Evaluation, and Parallel and Distributed Computing. Sung Je Hong, Ph.D.: He received the B.S. degree in Electronics Engineering from Seoul National University, Korea, in 1973, the M.S. degree in Computer Science from Iowa State University, Ames, U.S.A., in 1979, and the Ph.D. degree in Computer Science from the University of Illinois, Urbana, U.S.A., in 1983. He is currently a Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. From 1983 to 1989, he was a staff member of Corporate Research and Development, General Electric Company, Schenectady, NY, U.S.A. From 1975 to 1976, he was with Oriental Computer Engineering, Korea, as a Logic Design Engineer. His current research interest includes VLSI Design, CAD Algorithms, Testing, and Parallel Processing. Sunggu Lee, Ph.D.: He received the B.S.E.E. degree with highest distinction from the University of Kansas, Lawrence, in 1985 and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1987 and 1990, respectively. He is currently an Associate Professor in the Department of Electronic and Electrical Engineering at the Pohang University of Science and Technology (POSTECH), Pohang, Korea. Prior to this appointment, he was an Associate Professor in the Department of Electrical Engineering at the University of Delaware in Newark, Delaware, U.S.A. From June 1997 to July 1998, he spent one year as a Visiting Scientist at the IBM T. J. Watson Research Center. His research interests are in Parallel, Distributed, and Fault-Tolerant Computing. Currently, his main research focus is on the high-level and low-level aspects of Inter-Processor Communications for Parallel Computers.     

Scheduling real-time requests in on-demand data broadcast environments

On-demand broadcast is an attractive data dissemination method for mobile and wireless computing. In this paper, we propose a new online preemptive scheduling algorithm, called PRDS that incorporates urgency, data size and number of pending requests for real-time on-demand broadcast system. Furthermore, we use pyramid preemption to optimize performance and reduce overhead. A series of simulation experiments have been performed to evaluate the real-time performance of our algorithm as compared with other previously proposed methods. The experimental results show that our algorithm substantially outperforms other algorithms over a wide range of workloads and parameter settings. The work described in this paper was partially supported by grants from CityU (Project No. 7001841) and RGC CERG Grant No. HKBU 2174/03E. This paper is an extended version of the paper “A preemptive scheduling algorithm for wireless real-time on-demand data broadcast” that appeared in the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Victor C. S. Lee received his Ph.D. degree in Computer Science from the City University of Hong Kong in 1997. He is now an Assistant Professor in the Department of Computer Science of the City University of Hong Kong. Dr. Lee is a member of the ACM, the IEEE and the IEEE Computer Society. He is currently the Chairman of the IEEE, Hong Kong Section, Computer Chapter. His research interests include real-time data management, mobile computing, and transaction processing. Xiao Wu received the B.Eng. and M.S. degrees in computer science from Yunnan University, Kunming, China, in 1999 and 2002, respectively. He is currently a Ph.D. candidate in the Department of Computer Science at the City University of Hong Kong. He was with the Institute of Software, Chinese Academy of Sciences, Beijing, China, between January 2001 and July 2002. From 2003 to 2004, he was with the Department of Computer Science of the City University of Hong Kong, Hong Kong, as a Research Assistant. His research interests include multimedia information retrieval, video computing and mobile computing. Joseph Kee-Yin NG received a B.Sc. in Mathematics and Computer Science, a M.Sc. in Computer Science, and a Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in the years 1986, 1988, and 1993, respectively. Prof. Ng is currently a professor in the Department of Computer Science at Hong Kong Baptist University. His current research interests include Real-Time Networks, Multimedia Communications, Ubiquitous/Pervasive Computing, Mobile and Location- aware Computing, Performance Evaluation, Parallel and Distributed Computing. Prof. Ng is the Technical Program Chair for TENCON 2006, General Co-Chair for The 11th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), Program Vice Chair for The 11th International Conference on Parallel and Distributed Systems (ICPADS 2005), Program Area-Chair for The 18th & 19th International Conference on Advanced Information Networking and Applications (AINA 2004 & AINA 2005), General Co-Chair for The International Computer Congress 1999 & 2001 (ICC’99 & ICC’01), Program Co-Chair for The Sixth International Conference on Real-Time Computing Systems and Applications (RTCSA’99) and General Co-Chair for The 1999 and 2001 International Computer Science Conference (ICSC’99 & ICSC’01). Prof. Ng is a member of the Editorial Board of Journal of Pervasive Computing and Communications, Journal of Ubiquitous Computing and Intelligence, Journal of Embedded Computing, and Journal of Microprocessors and Microsystems. He is the Associate Editor of Real-Time Systems Journal and Journal of Mobile Multimedia. He is also a guest editor of International Journal of Wireless and Mobile Computing for a special issue on Applications, Services, and Infrastructures for Wireless and Mobile Computing. Prof. Ng is currently the Region 10 Coordinator for the Chapter Activities Board of the IEEE Computer Society, and is the Coordinator of the IEEE Computer Society Distinguished Visitors Program (Asia/Pacific). He is a senior member of the IEEE and has been a member of the IEEE Computer Society since 1991. Prof. Ng has been an Exco-member (1993–95), General Secretary (1995–1997), Vice-Chair (1997–1999), Chair (1999–2001) and the Past Chair of the IEEE, Hong Kong Section, Computer Chapter. Prof. Ng received the Certificate of Appreciation for Services and Contribution (2004) from IEEE Hong Kong Section, the Certificate of Appreciation for Leadership and Service (2000–2001) from IEEE Region 10 and the IEEE Meritorious Service Award from IEEE Computer Society at 2004. He is also a member of the IEEE Communication Society, ACM and the Founding Member for the Internet Society (ISOC)-Hong Kong Chapter.     

Approximation algorithm for periodic real-time tasks with workload-dependent running-time functions

This paper addresses the problem of resource allocation for distributed real-time periodic tasks, operating in environments that undergo unpredictable changes and that defy the specification of meaningful worst-case execution times. These tasks are supplied by input data originating from various environmental workload sources. Rather than using worst-case execution times (WCETs) to describe the CPU usage of the tasks, we assume here that execution profiles are given to describe the running time of the tasks in terms of the size of the input data of each workload source. The objective of resource allocation is to produce an initial allocation that is robust against fluctuations in the environmental parameters. We try to maximize the input size (workload) that can be handled by the system, and hence to delay possible (costly) reallocations as long as possible. We present an approximation algorithm based on first-fit and binary search that we call FFBS. As we show here, the first-fit algorithm produces solutions that are often close to optimal. In particular, we show analytically that FFBS is guaranteed to produce a solution that is at least 41% of optimal, asymptotically, under certain reasonable restrictions on the running times of tasks in the system. Moreover, we show that if at most 12% of the system utilization is consumed by input independent tasks (e.g., constant time tasks), then FFBS is guaranteed to produce a solution that is at least 33% of optimal, asymptotically. Moreover, we present simulations to compare FFBS approximation algorithm with a set of standard (local search) heuristics such as hill-climbing, simulated annealing, and random search. The results suggest that FFBS, in combination with other local improvement strategies, may be a reasonable approach for resource allocation in dynamic real-time systems. David Juedes is a tenured associate professor and assistant chair for computer science in the School of Electrical Engineering and Computer Science at Ohio University. Dr. Juedes received his Ph.D. in Computer Science from Iowa State University in 1994, and his main research interests are algorithm design and analysis, the theory of computation, algorithms for real-time systems, and bioinformatics. Dr. Juedes has published numerous conference and journal papers and has acted as a referee for IEEE Transactions on Computers, Algorithmica, SIAM Journal on Computing, Theoretical Computer Science, Information and Computation, Information Processing Letters, and other conferences and journals. Dazhang Gu is a software architect and researcher at Pegasus Technologies (NeuCo), Inc. He received his Ph.D. in Electrical Engineering and Computer Science from Ohio University in 2005. His main research interests are real-time systems, distributed systems, and resource optimization. He has published conference and journal papers on these subjects and has refereed for the Journal of Real-Time Systems, IEEE Transactions on Computers, and IEEE Transactions on Parallel and Distributed Systems among others. He also served as a session chair and publications chair for several conferences. Frank Drews is an Assistant Professor of Electical Engineering and Computer Science at Ohio Unversity. Dr. Drews received his Ph.D. in Computer Science from the Clausthal Unversity of Technolgy in Germany in 2002. His main research interests are resource management for operating systems and real-time systems, and bioinformatics. Dr. Drews has numerous publications in conferences and journals and has served as a reviewer for IEEE Transactions on Computers, the Journal of Systems and Software, and other conferences and Journals. He was Publication Chair for the OCCBIO’06 conference, Guest Editor of a Special Issue of the Journal of Systems and Software on “Dynamic Resource Management for Distributed Real-Time Systems”, organizer of special tracks at the IEEE IPDPS WPDRTS workshops in 2005 and 2006. Klaus Ecker received his Ph.D. in Theoretical Physics from the University of Graz, Austria, and his Dr. habil. in Computer Science from the University of Bonn. Since 1978 he is professor in the Department of Computer Science at the Clausthal University of Technology, Germany, and since 2005 he is visiting professor at the Ohio University. His research interests are parallel processing and theory of scheduling, especially in real time systems, and bioinformatics. Prof. Ecker published widely in the above mentioned areas in well reputed journals and proceedings of international conferences as well. He is also the author of two monographs on scheduling theory. Since 1981 he is organizing annually international workshops on parallel processing. He is associate editor of Real Time Systems, and member of the German Gesellschaft fuer Informatik (GI) and of the Association for Computing Machinery (ACM). Lonnie R. Welch received a Ph.D. in Computer and Information Science from the Ohio State University. Currently, he is the Stuckey Professor of Electrical Engineering and Computer Science at Ohio University. Dr. Welch performs research in the areas of real-time systems, distributed computing and bioinformatics. His research has been sponsored by the Defense Advanced Research Projects Agency, the Navy, NASA, the National Science Foundation and the Army. Dr. Welch has twenty years of research experience in the area of high performance computing. In his graduate work at Ohio State University, he developed a high performance 3-D graphics rendering algorithm, and he invented a parallel virtual machine for object-oriented software. For the past 15 years his research has focused on middleware and optimization algorithms for high performance computing. His research has produced three successive generations of adaptive resource management (RM) middleware for high performance real-time systems. The project has resulted in two patents and more than 150 publications. Professor Welch also collaborates on diabetes research with faculty at Edison Biotechnology Institute and on genomics research with faculty in the Department of Environmental and Plant Biology at Ohio University. Dr. Welch is a member of the editorial boards of IEEE Transactions on Computers, The Journal of Scalable Computing: Practice and Experience, and The International Journal of Computers and Applications. He is also the founder of the International Workshop on Parallel and Distributed Real-time Systems and of the Ohio Collaborative Conference on Bioinformatics. Silke Schomann graduated in 2003 with a M.Sc. in Computer Science from Clausthal University Of Technology, where she has been working as a scientific assistant since then. She is currently working on her Ph.D. thesis in computer science at the same university.     

Circular attribute grammars with remote attribute references and their evaluators

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as “goto” in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposescircular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called amostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators. Akira Sasaki: He is a research fellow of the Advanced Clinical Research Center in the Institute of Medical Science at the University of Tokyo. He received his BSc and MSc from Tokyo Institute of Technology, Japan, in 1994 and 1996, respectively. His research interests include programming languages, programming language processors and programming environments, especially compiler compilers, attribute grammars and systematic debugging. He is a member of the Japan Society for Software Science and Technology. Masataka Sassa, D.Sc.: He is Professor of Computer Science at Tokyo Institute of Technology. He received his BSc, MSc and DSc from the University of Tokyo, Japan, in 1970, 1972 and 1978, respectively. His research interests include programming languages, programming language processors and programming environments, currently he is focusing on compiler optimization, compiler infrastructure, attribute grammars and systematic debugging. He is a member of the ACM, IEEE Computer Society, Japan Society for Software Science and Technology, and Information Processing Society of Japan.     

Interactive learning and management of visual information via human-like software robot

To achieve smooth real-world interaction between people and computers, we developed a system that displays a three-dimensional computer-graphic human-like image from the waist up (anthropomorphic software robot: hereinafter “robot”) on the display, that interactively sees and hears, and that has fine and detailed control functions such as facial expressions, line of sight, and pointing at targets with its finger. The robot visually searches and identifies persons and objects in real space that it has learned in advance (registered space, which was our office in this case), manages the history information of the places and times it found objects and/or persons, and tells the user, indicating their three-dimensional positions with line of sight and its finger. It interactively learns new objects and persons with line of with their names and owners. By using this function, the robot can engage in simple dialogue (do a task) with the user. Osamu Hasegawa, Ph.D.: He received the B.E. and M.E. degrees from the Science University of Tokyo, in 1988, 1990 respectively. He received Ph.D. degree from the University of Tokyo, in 1993. Currently, he is a senior research scientist at the Electrotechnical Laboratory (ETL), Tsukuba, Japan. His research interests include Computer Vision and Multi-modal Human Interface. Dr. Hasegawa is a member of the AAAI, the Institute of Electronics, Information and Communication Engineers, Japan (IEICE), Information Processing Society of Japan and others. Katsuhiko Sakaue, Ph.D.: He received the B.E., M.E., and Ph.D. degrees all in electronic engineering from the University of Tokyo, in 1976, 1978 and 1981, respectively. In 1981, he joined the Electrotechnical Laboratory, Ministry of International Trade and Industry, and engaged in researches in image processing and computer vision. He received the Encouragement Prize in 1979 from IEICE, and the Paper Award in 1985 from Information Processing Society of Japan. He is a member of IEICE, IEEE, IPSJ, ITE. Satoru Hayamizu, Ph.D.: He is a leader of Interactive Intermodal Integration Lab. at Electrotechnical Laboratory. He received the B.E., M.E., Ph.D. degrees from Tokyo University. Since 1981, he has been working on speech recognition, spoken dialogue, and communication with artifacts. From 1989 to 1990, he was a visiting scholar in Carnegie Mellon University and in 1994 a visiting scientist in LIMSI/CNRS.     

Pitch-Dependent Identification of Musical Instrument Sounds

This paper describes a musical instrument identification method that takes into consideration the pitch dependency of timbres of musical instruments. The difficulty in musical instrument identification resides in the pitch dependency of musical instrument sounds, that is, acoustic features of most musical instruments vary according to the pitch (fundamental frequency, F0). To cope with this difficulty, we propose an F0-dependent multivariate normal distribution, where each element of the mean vector is represented by a function of F0. Our method first extracts 129 features (e.g., the spectral centroid, the gradient of the straight line approximating the power envelope) from a musical instrument sound and then reduces the dimensionality of the feature space into 18 dimension. In the 18-dimensional feature space, it calculates an F0-dependent mean function and an F0-normalized covariance, and finally applies the Bayes decision rule. Experimental results of identifying 6,247 solo tones of 19 musical instruments shows that the proposed method improved the recognition rate from 75.73% to 79.73%. This research was partially supported by the Ministry of Education, Culture, Sports, Science and Technology (MEXT), Grant-in-Aid for Scientific Research (A), No.15200015, and Informatics Research Center for Development of Knowledge Society Infrastructure (COE program of MEXT, Japan). Tetsuro Kitahara received the B.S. from Tokyo University of Science in 2002 and the M.S. from Kyoto University in 2004. He is currently a Ph.D. course student at Graduate School of Informatics, Kyoto University. Since 2005, he has been a Research Fellow of the Japan Society for the Promotion of Science. His research interests include music informatics. He recieved IPSJ 65th National Convention Student Award in 2003, IPSJ 66th National Convention Student Award and TELECOM System Technology Award for Student in 2004, and IPSJ 67th National Convention Best Paper Award for Young Researcher in 2005. He is a student member of IPSJ, IEICE, JSAI, ASJ, and JSMPC. Masataka Goto received his Doctor of Engineering degree in Electronics, Information and Communication Engineering from Waseda University, Japan, in 1998. He then joined the Electrotechnical Laboratory (ETL; reorganized as the National Institute of Advanced Industrial Science and Technology (AIST) in 2001), where he has been engaged as a researcher ever since. He served concurrently as a researcher in Precursory Research for Embryonic Science and Technology (PRESTO), Japan Science and Technology Corporation (JST) from 2000 to 2003, and an associate professor of the Department of Intelligent Interaction Technologies, Graduate School of Systems and Information Engineering, University of Tsukuba since 2005. His research interests include music information processing and spoken language processing. Dr. Goto received seventeen awards including the IPSJ Best Paper Award and IPSJ Yamashita SIG Research Awards (MUS and SLP) from the Information Processing Society of Japan (IPSJ), Awaya Prize for Outstanding Presentation and Award for Outstanding Poster Presentation from the Acoustical Society of Japan (ASJ), Award for Best Presentation from the Japanese Society for Music Perception and Cognition (JSMPC), WISS 2000 Best Paper Award and Best Presentation Award, and Interaction 2003 Best Paper Award. He is a member of the IPSJ, ASJ, JSMPC, Institute of Electronics, Information and Communication Engineers (IEICE), and International Speech Communication Association (ISCA). Hiroshi G. Okuno received the B.A. and Ph.D from the University of Tokyo in 1972 and 1996, respectively. He worked for Nippon Telegraph and Telephone, Kitano Symbiotic Systems Project, and Tokyo University of Science. He is currently a professor at the Department of Intelligence Technology and Science, Graduate School of Informatics, Kyoto University. He was a visiting scholar at Stanford University, and a visiting associate professor at the University of Tokyo. He has done research in programming languages, parallel processing, and reasoning mechanism in AI, and he is currently engaged in computational auditory scene analysis, music scene analysis and robot audition. He received the best paper awards from the Japanese Society for Artificial Intelligence and the International Society for Applied Intelligence, in 1991 and 2001, respectively. He edited with David Rosenthal “Computational Auditory Scene Analysis” from Lawrence Erlbaum Associates in 1998 and with Taiichi Yuasa “Advanced Lisp Technology” from Taylor and Francis Inc. in 2002. He is a member of IPSJ, JSAI, JSSST, JSCS, ACM, AAAI, ASA, and IEEE.     

Transformation rules for CNOT-based quantum circuits and their applications

This paper introduces a simple but nontrivial set of local transformation rules for designingControl-NOT(CNOT)-based combinatorial circuits. We also provide a proof that the rule set iscomplete, namely, for any two equivalent circuits,S ₁ andS ₂, there is a sequence of transformations, each of them in the rule set, which changesS ₁ toS ₂. Two applications of the rule set are also presented. One is to simulate Resolution with only polynomial overhead by the rule set. Therefore we can conclude that the rule set is reasonably powerful. The other is to reduce the cost of CNOT-based circuits by using the transformations in the rule set. This implies that the rule set might be used for the practical circuit design. Currently Graduate School of Information Science, Nara Institute of Science and Technology Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Shigeru Yamashita, Ph.D.: Associate Professor of Graduate School of Information Science, Nara Instutute of Science and Technology, Nara 630-0192, Japan. He received his B.E., M.E. and Ph.D. degrees in information science from Kyoto University, Kyoto, Japan, in 1993, 1995 and 2001, respectively. His research interests include new type of computer architectures and quantum computation. He received the 2000 IEEE Circuits and Systems Society Transactions on Computer-Aided Design of Integrated Circuits and Systems Best Paper Award.     

A unified architecture for agent behaviors with selection of evolved neural network modules

To model complex systems for agent behaviors, genetic algorithms have been used to evolve neural networks which are based on cellular automata. These neural networks are popular tools in the artificial life community. This hybrid architecture aims at achieving synergy between the cellular automata and the powerful generalization capabilities of the neural networks. Evolutionary algorithms provide useful ways to learn about the structure of these neural networks, but the use of direct evolution in more difficult and complicated problems often fails to achieve satisfactory solutions. A more promising solution is to employ incremental evolution that reuses the solutions of easy tasks and applies these solutions to more difficult ones. Moreover, because the human brain can be divided into many behaviors with specific functionalities and because human beings can integrate these behaviors for high-level tasks, a biologically-inspired behavior selection mechanism is useful when combining these incrementally evolving basic behaviors. In this paper, an architecture based on cellular automata, neural networks, evolutionary algorithms, incremental evolution and a behavior selection mechanism is proposed to generate high-level behaviors for mobile robots. Experimental results with several simulations show the possibilities of the proposed architecture. Kyung-Joong Kim (Student Member, IEEE) received the B.S. and M.S. degree in computer science from Yonsei University, Seoul, Korea, in 2000 and 2002, respectively. Since 2002, he has been a Ph.D. student in the Department of Computer Science, Yonsei University. His research interests include evolutionary neural network, robot control, and agent architecture. Sung-Bae Cho (Member, IEEE) received the B.S. degree in computer science from Yonsei University, Seoul, Korea, in 1988 and the M.S. and Ph.D. degrees in computer science from Korea Advanced Institute of Science and Technology (KAIST), Taejeon, Korea, in 1990 and 1993, respectively. From 1991 to 1993, he worked as a Member of the Research Staff at the Center for Artificial Intelligence Research at KAIST. From 1993 to 1995, he was an Invited Researcher of Human Information Processing Research Laboratories at ATR (Advanced Telecommunications Research) Institute, Kyoto, Japan. In 1998, he was a Visiting Scholar at University of New South Wales, Canberra, Australia. Since 1995, he has been a Professor in the Department of Computer Science, Yonsei University. His research interests include neural networks, pattern recognition, intelligent man-machine interfaces, evolutionary computation, and artificial life. Dr. Cho is a Member of the Korea Information Science Society, INNS, the IEEE Computer Society, and the IEEE Systems, Man and Cybernetics Society. He was awarded outstanding paper prizes from the IEEE Korea Section in 1989 and 1992, and another one from the Korea Information Science Society in 1990. In 1993, he also received the Richard E. Merwin prize from the IEEE Computer Society. In 1994, he was listed in Who’s Who in Pattern Recognition from the International Association for Pattern Recognition and received the best paper awards at International Conference on Soft Computing in 1996 and 1998. In 1998, he received the best paper award at World Automation Congress. He was listed in Marquis Who’s Who in Science and Engineering in 2000 and in Marquis Who’s Who in the World in 2001.