Polynomial-time learning of elementary formal systems

An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We investigate EFSs for polynomial-time PAC-learnability. A definite clause of an EFS is hereditary if every pattern in the body is a subword of a pattern in the head. With this new notion, we show that H-EFS(m, k, t, r) is polynomial-time learnable, which is the class of languages definable by EFSs consisting of at mostm hereditary definite clauses with predicate symbols of arity at mostr, wherek andt bound the number of variable occurrences in the head and the number of atoms in the body, respectively. The class defined by all finite unions of EFSs in H-EFS(m, k, t, r) is also polynomial-time learnable. We also show an interesting series ofNC-learnable classes of EFSs. As hardness results, the class of regular pattern languages is shown not polynomial-time learnable unlessRP=NP. Furthermore, the related problem of deciding whether there is a common subsequence which is consistent with given positive and negative examples is shownNP-complete. Satoru Miyano, Dr. Sci.: He is a Professor in Human Genome Center at the University of Tokyo. He obtained B.S. in 1977, M.S. in 1979, and Dr. Sci. degree all in Mathematics from Kyushu University. His current interests include bioinformatics, discovery science, computational complexity, computational learning. He has been organizing Genome Informatics Workshop Series since 1996 and has served for the chair/member of the program committee of many conferences in the area of Computer Science and Bioinformatics. He is on the Editorial Board of Theoretical Computer Science and the Chief Editor of Genome Informatics Series. Ayumi Shinohara, Dr. Sci.: He is an Associate Professor in the Department of Informatics at Kyushu University. He obtained B.S. in 1988 in Mathematics, M.S. in 1990 in Information Systems, and Dr. Sci. degree in 1994 all from Kyushu University. His current interests include discovery science, bioinformatics, and pattern matching algorithms. Takeshi Shinohara, Dr. Sci.: He is a Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his B.S. in Mathematics from Kyoto University in 1980, and his Dr. Sci. degree from Kyushu University in 1986. His research interests are in Computational/Algorithmic Learning Theory, Information Retrieval, and Approximate Retrieval of Multimedia Data.     

A grid-oriented genetic algorithm framework for bioinformatics

In this paper, we propose a framework for enabling for researchers of genetic algorithms (GAs) to easily develop GAs running on the Grid, named “Grid-Oriented Genetic algorithms (GOGAs)”, and actually “Gridify” a GA for estimating genetic networks, which is being developed by our group, in order to examine the usability of the proposed GOGA framework. We also evaluate the scalability of the “Gridified” GA by applying it to a five-gene genetic network estimation problem on a grid testbed constructed in our laboratory. Hiroaki Imade: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2001. He received the M.S. degree in information systems from the Graduate School of Engineering, The University of Tokushima in 2003. He is now in Doctoral Course of Graduate School of Engineering, The University of Tokushima. His research interests include evolutionary computation. He currently researches a framework to easily develop the GOGA models which efficiently work on the grid. Ryohei Morishita: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2002. He is now in Master Course of Graduate School of Engineering, The University of Tokushima, Tokushima. His research interest is evolutionary computation. He currently researches GA for estimating genetic networks. Isao Ono, Ph.D.: He received his B.S. degree from the Department of Control Engineering, Tokyo Institute of Technology, Tokyo, Japan, in 1994. He received Ph.D. of Engineering at Tokyo Institute of Technology, Yokohama, in 1997. He worked as a Research Fellow from 1997 to 1998 at Tokyo Institute of Technology, and at University of Tokushima, Tokushima, Japan, in 1998. He worked as a Lecturer from 1998 to 2001 at University of Tokushima. He is now Associate Professor at University of Tokushima. His research interests include evolutionary computation, scheduling, function optimization, optical design and bioinformatics. He is a member of JSAI, SCI, IPSJ and OSJ. Norihiko Ono, Ph.D.: He received his B.S. M.S. and Ph.D. of Engineering in 1979, 1981 and 1986, respectively, from Tokyo Institute of Technology. From 1986 to 1989, he was Research Associate at Faculty of Engineering, Hiroshima University. From 1989 to 1997, he was an associate professor at Faculty of Engineering, University of Tokushima. He was promoted to Professor in the Department of Information Science and Intelligent Systems in 1997. His current research interests include learning in multi-agent systems, autonomous agents, reinforcement learning and evolutionary algorithms. Masahiro Okamoto, Ph.D.: He is currently Professor of Graduate School of Systems Life Sciences, Kyushu University, Japan. He received his Ph.D. degree in Biochemistry from Kyushu University in 1981. His major research field is nonlinear numerical optimization and systems biology. His current research interests cover system identification of nonlinear complex systems by using evolutional computer algorithm of optimization, development of integrated simulator for analyzing nonlinear dynamics and design of fault-tolerant routing network by mimicking metabolic control system. He has more than 90 peer reviewed publications.     

A quantum algorithm using NMR computers to break secret-key cryptosystems

In this paper, we discuss quantum algorithms that, for a given plaintextm _o and a given ciphertextc _o, will find a secret key,k _o, satisfyingc _o=E(k _o,m _o), where an encryption algorithm,E, is publicly available. We propose a new algorithm suitable for an NMR (Nuclear Magnetic Resonance) computer based on the technique used to solve the counting problem. The complexity of, our algorithm decreases as the measurement accuracy of the NMR computer increases. We discuss the possibility that the proposed algorithm is superior to Grover’s algorithm based on initial experimental results. Kazuo Ohta, Dr.S.: He is Professor of Faculty of Electro-Communications at the University of Electro-Communications, Japan. He received B.S., M.S., and Dr. S. degrees from Waseda University, Japan, in 1977, 1979, and 1990, respectively. He was researcher of NTT (Nippon Telegraph and Telephone Corporation) from 1979 to 2001, and was visiting scientist of Laboratory for Computer Science e of MIT (Massachusetts Institute of Technology) in 1991–1992 and visiting Professor of Applied Mathematics of MIT in 2000. He is presently engaged in research on Information Security, and theoretical computer science. Dr. Ohta is a member of IEEE, the International Association for Cryptologic Research, the Institute of Electronics, Information and Communication Engineers and the Information Processing Society of Japan. Tetsuro Nishino,: He received the B.S., M.S. and, D.Sc. degrees in mathematics from Waseda University, in 1982, 1984, and 1991 respectively. From 1984 to 1987, he joined Tokyo Research Laboratory, IBM Japan. From 1987 to 1992, he was a Research Associate of Tokyo Denki University, and from 1992 to 1994, he was an Associate Professor of Japan Advanced Institute of Science and Technology, Hokuriku. He is presently an Associate Professor in the Department of Communications and Systems Engineering, the University of Electro-Communications. His main interests are circuit complexity theory, computational learning theory and quantum complexity theory. Seiya Okubo,: He received the B.Eng. and M.Eng. degrees from the University of Electro-Communications in 2000 and 2002, respectively. He is a student in Graduate School of Electro-Communications, the University of Electro-Communications. His research interests include quantum complexity theory and cryptography. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B. E., M. E. and Ph. D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interests include cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize.     

The superstructure toward open bioinformatics grid

The grid design strongly depends on not only a network infrastructure but also a superstructure, that is, a social structure of virtual organizations where people trust each other, share resources and work together. Open Bioinformatics Grid (OBIGrid) is a grid aimed at building a cooperative bioinformatics environment for computer sicentists and biologists. In October 2003, OBIGrid consisted of 293 nodes with 492 CPUs provided by 27 sites at universities, laboratories and other enterprises, connected by a virtual private network over the Internet. So many organizations have participated because OBIGrid has been conscious of constructing a superstructure on a grid as well as a grid infrastructure. For the benefit of OBIGrid participants, we have developed a series of life science application services: an open bioinformatics environment (OBIEnv), a scalable genome database (OBISgd), a genome annotation system (OBITco), a biochemical network simulator (OBIYagns), and to name a few. Akihiko Konagaya, Dr.Eng.: He is Project Director of Bioinformatics Group, RIKEN Genomic Sciences Center. He received his B.S. and M.S. from Tokyo Institute of Technology in 1978 and 1980 in Informatics Science, and joined NEC Corporation in 1980, Japan Advanced Institute of Science and Technology in 1997, RIKEN GSC in 2003. His research covers wide area from computer architectures to bioinformatics. He has been much involved into the Open Bioinformatics Grid project since 2002. Fumikazu Konishi, Dr.Eng.: He is researcher at Bioinformatics Group, RIKEN Genomic Sciences Center since 2000. He received his M.S. (1996) and Ph.D. (2001) from Tokyo Metropolitan Institute of Technology. He served as an assistant in Department of Production and Information Systems Engineering, Tokyo Metropolitan Institute of Technology since 2000. He also works in Structurome Research Group, RIKEN Harima Institute from 2001. His research interests include concurrent engineering, bioinformatics and the Grid. He has deeply affected to the design of OBIGrid. Mariko Hatakeyama, Ph.D.: She recieved her Ph.D. degree from Tokyo University of Agriculture and Technology. She is Research Scientist at Bioinformactis Group, RIKEN Genomic Sciences Center. Her research topics are: microbiology, enzymology and signal transduction of mammalian cells. She is now working on computational simulation of signal transduction systems and on thermophilic bacteria project. Kenji Satou, Ph.D.: He is Associate Professor of School of Knowledge Science at Japan Advanced Institute of Science and Technology. He received B.S., M.E. and Ph.D. degrees from Kyushu University, in 1987, 1989 and 1995 respectively. For each degree, he majored in computer engineering. His research interests have progressed from deductive database application through data mining to Grid computing and natural language processing. His current field of research is bioinformatics. He prefers set-oriented manner of thinking, and usually wonders how he can construct an intelligent-looking system based on large amount of heterogeneous data and computer resources.     

Generation of templates for low-resolution text recognition using a hypothesis graph

We propose a recognition method of character-string images captured by portable digital cameras. A challenging task in character-string recognition is the segmentation of characters. In the proposed method, a hypothesis graph is used for recognition-based segmentation of the character-string images. The hypothesis graph is constructed by the subspace method, using eigenvectors as conditionally elastic templates. To obtain these templates, a generation-based approach is introduced in the training stage. Various templates are generated to cope with low-resolution. We have experimentally proved that the proposed scheme achieves high recognition performance even for low-resolution character-string images. The text was submitted by the authors in English. Hiroyuki Ishida. Received his B.S. and M.S. degrees from the Department of Information Engineering and from the Graduate School of Information Science, respectively, at Nagoya University. He is currently pursuing a Ph.D. in Information Science at Nagoya University. Ichiro Ide. Received his B.S. degree from the Department of Electronic Engineering, his M.S. degree from the Department of Information Engineering, and his Ph.D. from the Department of Electrical Engineering at the University of Tokyo. He is currently an Associate Professor in the Graduate School of Information Science at Nagoya University. Tomokazu Takahashi. Received his B.S. degree from the Department of Information Engineering at Ibaraki University, and his M.S. and Ph.D. from the Graduate School of Science and Engineering at Ibaraki University. His research interests include computer graphics and image recognition. Hiroshi Murase. Received his B.S., M.S., and Ph.D. degrees from the Graduate School of Electrical Engineering at Nagoya University. He is currently a Professor in the Graduate School of Information Science at Nagoya University. He received the Ministry Award from the Ministry of Education, Culture, Sports, Science and Technology in Japan in 2003. He is a Fellow of the IEEE.     

Efficient minimum spanning tree algorithms on the reconfigurable mesh

1 IntroductionLet G = (V, E) be a connected, undirected graph with a weight function W on the set Eof edges to the set of reals. A spanning tree is a subgraph T = (V, ET), ET G E, of C suchthat T is a tree. The weight W(T) of a spanning tree T is the sum of the weights of its edges.A spanning tree with the smallest possible'weight is called a minimum spanning tree (MST)of G. Computing an MST of a given weighted graph is an important problem that arisesin many applications. For this …     

An efficient parallel graph edge matching algorithm and its applications

A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graphG(V,E) is proposed.It runs in O(log n)time with O(m,/log n n)processors on an EREW PRAM for a class of graph set П,where n=|V|,m=|E|and П includes at least (i)planar graphs;(ii) graphs of bounded genus;and (iii)graphs of bounded maximum degress and so on.Our algorithm improves the previously known best algorithms by a factor of logn in the time complexity with linear number of processors on EREW PRAMs when the input is limited to П.     

A Model for Slicing JAVA Programs Hierarchically

Program slicing can be effectively used to debug, test, analyze, understand and maintain objectoriented software. In this paper, a new slicing model is proposed to slice Java programs based on their inherent hierarchical feature. The main idea of hierarchical slicing is to slice programs in a stepwise way, from package level, to class level, method level, and finally up to statement level. The stepwise slicing algorithm and the related graph reachability algorithms are presented, the architecture of the Java program Analyzing TOol (JATO) based on hierarchical slicing model is provided, the applications and a small case study are also discussed.     

A Fuzzy set based approach to generalized landscape theory of aggregation

In this paper, we firstly reformulate the landscape theory of aggregation (Axelrod and Bennett, 1993) in terms of an optimization problem, and then straightforwardly propose a fuzzy-set-theoretic based extension for it. To illustrate efficiency of the proposal, we make a simulation with the proposed framework for the international alignment of the Second World War in Europe. It is shown that the obtained results are essentially comparable to those given by the original theory. Consequently, the fuzzy-set-theoretic based extension of landscape theory can allow us to analyze a wide variety of aggregation processes in politics, economics, and society in a more flexible manner. Shigemasa Suganuma: He received the M.S. degree in knowledge science from Japan Advanced Institute of Science and Technology,, Ishikawa, Japan in 2000. He currently takes a doctor's course in School of Knowledge Science, Japan Advanced Institute of Science and Technology (JAIST). His research interest includes agent based simulation and its application to social and political concerns, industry and environmental behavior. Van-Nam Huynh, Ph.D.: He received the B.S. in Mathematics (1990) and Ph.D. (1999) from University of Quinhon, Vietnam and Institute of Information Technology, Vietnam Academy of Science and Technology, respectively. From April 2001 to March 2002, he was a postdoctoral fellow awarded by INOUE Foundation for Science at JAIST. He is currently a Research Associate in School of Knowledge Science, JAIST, Japan. His current research interests include fuzzy logic and approximate reasoning, uncertainty formalisms in knowledge-based systems, decision making. Yoshiteru Nakamori, Ph.D.: He received the B.S., M.S., and Ph.D. degrees all in applied mathematics and physics from Kyoto University, Kyoto, Japan. He is currently a Professor in School of Knowledge Science, JAIST. His research interests include development of modeling methodology based on hard as well as soft data, and support systems for soft thinking around hard data. Shouyang Wang, Ph.D.: He received the Ph.D. degree in Operations Research from Chinsese Academy of Sciences (CAS), Beijing in 1986. He is currently a Bairen distinguished professor of Management Science at Academy of Mathematics and Systems Sciences of CAS and a Lotus chair professor of Hunan University in Changsha. He is the editor-in-chief or a co-editor of 12 journals. He has published 120 journal articles. His current research interest includes decision analysis, system engineering and knowledge management.     

Automatic transaction of signal via statistical modeling

The statistical information processing can be characterized by the likelihood function defined by giving an explicit form for an approximation to the true distribution. This mathematical representation, which is usually called a model, is built based on not only the current data but also prior knowledge on the object and the objective of the analysis. Akaike^2,3) showed that the log-likelihood can be considered as an estimate of the Kullback-Leibler (K-L) information which measures the similarity between the predictive distribution of the model and the true distribution. Akaike information criterion (AIC) is an estimate of the K-L information and makes it possible to evaluate and compare the goodness of many models objectively. In consequence, the minimum AIC procedure allows us to develop automatic modeling and signal extraction procedures. In this article, we give a simple explanation of statistical modeling based on the AIC and demonstrate four examples of applying the minimum AIC procedure to an automatic transaction of signals observed in the earth sciences. Genshiro, Kitagawa, Ph.D.: He is a Professor in the Department of Prediction and Control at the Institute of Statistical Mathematics. He is currently Deputy Director of the Institute of Statistical Mathematics and Professor of Statistical Science at the Graduate University for Advanced Study. He obtained his Ph.D. from the Kyushu University in 1983. His primary research interests are in time series analysis, non-Gaussian nonlinear filtering, and statistical modeling. He has published over 50 research papers. He was awarded the 2nd Japan Statistical Society Prize in 1997. Tomoyuki Higuchi, Ph.D.: He is an Associate Professor in the Department of Prediction and Control at the Institute of Statistical Mathematics. He is currently an Associate Professor of Statistical Science at the Graduate University for Advanced Study. He obtained his Ph.D. from the University of Tokyo in 1989. His research interests are in statistical modeling of space-time data, stochastic optimization techniques, and data mining. He has published over 30 research papers.     

Nonlinear adaptive decentralized stabilization control for multimachine power systems

This paper presents a decentralized adaptive backstepping controller to dampen oscillations and improve the transient stability to parametric uncertainties in multimachine power systems. The proposed design on the i ^th synchronous generator uses only local information and operates without the need for remote signals from the other generators. The design of the nonlinear controller is based on a modified fourth-order nonlinear model of a synchronous generator, and the automatic voltage regulator model is considered so as to decrease the steady state voltage error. The construction of both the control law and the associated Lyapunov function is systematically designed within the design methodology. A 3-machine power system is used to demonstrate the effectiveness of the proposed controller over two other controllers, namely a conventional damping controller (power system stabilizer) and one designed using the feedback linearization techniques. Recommended by Editorial Board member Gang Tao under the direction of Editor Jae Weon Choi. This work was supported by the Korea Electrical Engineering and Science Research Institute, which is funded by Ministry of Commerce, Industry and Energy. Shan-Ying Li received the B.S. degrees in Computer Science and M.S. degree in Electrical Engineering from Northeast DianLi University, China, in 1997 and 2002, respectively. She obtained the Ph.D. degree in Electrical Engineering from Seoul National University, Korea, in 2008. She is a Post Doctor in North China Electric Power Research Institute, North China Grid Co., Ltd., China. Her research interests are in the areas of advanced control and stability applications on power systems. Sang-Seung Lee received the M.S.E.E. and Ph.D. degrees in Electrical Engineering at Seoul National University. Currently, he is with Power System Research Division of KESRI, Seoul National University, Korea. His interest areas are nonlinear/adaptive control theory, North-East Asia power system interconnection, distributed/small generation, distributed transmission/distribution load flow algorithm, regional/local energy system, PSS (power system stabilizer), and RCM (Reliability Centered Maintenance). Yong Tae Yoon was born in Korea on April 20, 1971. He received the B.S. degree, M.Eng. and Ph.D. degrees from M.I.T., USA in 1995, 1997, and 2001, respectively. Currently, he is an Assistant Professor in the School of Electrical Engineering and Computer Science at Seoul National University, Korea. His special field of interest includes electric power network economics, power system reliability, and the incentive regulation of independent transmission companies. Jong-Keun Park received the B.S. degree in Electrical Engineering from Seoul National University, Seoul, Korea in 1973 and the M.S. and Ph.D. degrees in Electrical Engineering from The University of Tokyo, Japan in 1979 and 1982, respectively. He is currently a Professor of School of Electrical Engineering, Seoul National University. In 1992, he attended as a Visiting Professor at Technology and Policy Program and Laboratory for Electromagnetic and Electronic Systems, Massachusetts Institute of Technology. He is a Senior Member of the IEEE, a Fellow of the IEE, and a Member of Japan Institute of Electrical Engineers (JIEE).     

Oscillation amplitude-controlled resonant accelerometer design using a reference tracking automatic gain control

In this paper, it is presented a novel approach for the self-sustained resonant accelerometer design, which takes advantages of an automatic gain control in achieving stabilized oscillation dynamics. Through the proposed system modeling and loop transformation, the feedback controller is designed to maintain uniform oscillation amplitude under dynamic input accelerations. The fabrication process for the mechanical structure is illustrated in brief. Computer simulation and experimental results show the feasibility of the proposed accelerometer design, which is applicable to a control grade inertial sense system. Recommended by Editorial Board member Dong Hwan Kim under the direction of Editor Hyun Seok Yang. This work was supported by the BK21 Project ST·IT Fusion Engineering program in Konkuk University, 2008. This work was supported by the Korea Foundation for International Cooperation of Science & Technology(KICOS) through a grant provided by the Korean Ministry of Education, Science & Technology(MEST) in 2008 (No. K20601000001). Authors also thank to Dr. B.-L. Lee for the help in structure manufacturing. Sangkyung Sung is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the M.S and Ph.D. degrees in Electrical Engineering from Seoul National University in 1998 and 2003, respectively. His research interests include inertial sensors, avionic system hardware, navigation filter, and intelligent vehicle systems. Chang-Joo Kim is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aeronautical Engineering from Seoul National University in 1991. His research interests include nonlinear optimal control, helicopter flight mechanics, and helicopter system design. Young Jae Lee is a Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aerospace Engineering from the University of Texas at Austin in 1990. His research interests include integrity monitoring of GNSS signal, GBAS, RTK, attitude determination, orbit determination, and GNSS related engineering problems. Jungkeun Park is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University. Dr. Park received the Ph.D. in Electrical Engineering and Computer Science from the Seoul National University in 2004. His current research interests include embedded real-time systems design, real-time operating systems, distributed embedded real-time systems and multimedia systems. Joon Goo Park is an Assistant Professor of the Department of Electronic Engineering at Gyung Book National University, Korea. He received the Ph.D. degree in School of Electrical Engineering from Seoul National University in 2001. His research interests include mobile navigation and adaptive control.     

Approximate retrieval of high-dimensional data withL 1 metric by spatial indexing

High-dimensional data, such as documents, digital images, and audio clips, can be considered as spatial objects, which induce a metric space where the metric can be used to measure dissimilarities between objects. We investigate a method for retrieving objects within some distance from a given object by utilizing a spatial indexing/access method R-tree, which usually assumes Euclidean metric. First, we prove that objects in discreteL ₁ (or Manhattan distance) metric space can be embedded into vertices of a unit hyper-cube in Euclidean space when the square root ofL ₁ distance is used as the distance. To take fully advantage of R-tree spatial indexing, we have to project objects into space of relatively lower dimension. We adopt FastMap by Faloutsos and Lin to reduce the dimension of object space. The range corresponding to a query (Q, h) for retrieving objects within distanceh from a objectQ is naturally considered as a hyper-sphere even after FastMap projection, which is an orthogonal projection in Euclidean space. However, it is turned out that the query range is contracted into a smaller hyper-box than the hyper-sphere by applying FastMap to objects embedded in the above mentioned way. Finally, we give a brief summary of experiments in applying our method to Japanese chess boards. Takeshi Shinohara, Dr.Sci.: He is a Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his bachelors degree in Mathematics from Kyoto University in 1980, and his Dr. Sci. from Kyushu University in 1986. His research interests are in Computational/Algorithmic Learning Theory, Information Retrieval, and Approximate Retrieval of Multimedia Data. Hiroki Ishizaka, Dr.Sci.: He is an Associate Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his bachelors degree in Mathematics from Kyushu University in 1984, and his Dr.Sci. from Kyushu University in 1993. His research interests are in Computational/Algorithmic Learning Theory.     

A challenge towards next-generation research infrastructure for advanced life science

Recently, life scientists have expressed a strong need for computational power sufficient to complete their analyses within a realistic time as well as for a computational power capable of seamlessly retrieving biological data of interest from multiple and diverse bio-related databases for their research infrastructure. This need implies that life science strongly requires the benefits of advanced IT. In Japan, the Biogrid project has been promoted since 2002 toward the establishment of a next-generation research infrastructure for advanced life science. In this paper, the Biogrid strategy toward these ends is detailed along with the role and mission imposed on the Biogrid project. In addition, we present the current status of the development of the project as well as the future issues to be tackled. Haruki Nakamura, Ph.D.: He is Professor of Protein Informatics at Institute for Protein Research, Osaka University. He received his B.S., M.A. and Ph.D. from the University of Tokyo in 1975, 1977 and 1980 respectively. His research field is Biophysics and Bioinformatics, and has so far developed several original algorithms in the computational analyses of protein electrostatic features and folding dynamics. He is also a head of PDBj (Protein Data Bank Japan) to manage and develop the protein structure database, collaborating with RCSB (Research Collaboratory for Structural Bioinformatics) in USA and MSD-EBI (Macromolecular Structure Database at the European Bioinformatics Institute) in EU. Susumu Date, Ph.D.: He is Assistant Professor of the Graduate School of Information Science and Technology, Osaka University. He received his B.E., M.E. and Ph.D. degrees from Osaka University in 1997, 2000 and 2002, respectively. His research field is computer science and his current research interests include application of Grid computing and related information technologies to life sciences. He is a member of IEEE CS and IPSJ. Hideo Matsuda, Ph.D.: He is Professor of the Department of Bioinformatic Engineering, the Graduate School of Information Science and Technology, Osaka University. He received his B.S., M.Eng. and Ph.D. degrees from Kobe University in 1982, 1984 and 1987 respectively. For M.Eng. and Ph.D. degrees, he majored in computer science. His research interests include computational analysis of genomic sequences. He has been involved in the FANTOM (Functional Annotation of Mouse) Project for the functional annotation of RIKEN mouse full-length cDNA sequences. He is a member of ISCB, IEEE CS and ACM. Shinji Shimojo, Ph.D.: He received M.E. and Ph.D. degrees from Osaka University in 1983 and 1986 respectively. He was an Assistant Professor with the Department of Information and Computer Sciences, Faculty of Engineering Science at Osaka University from 1986, and an Associate Professor with Computation Center from 1991 to 1998. During the period, he also worked as a visiting researcher at the University of California, Irvine for a year. He has been Professor with Cybermedia Center (then Computation Center) at Osaka University since 1998. His current research work focus on a wide variety of multimedia applications, peer-to-peer communication networks, ubiquitous network systems and Grid technologies. He is a member of ACM, IEEE and IEICE.     

LMI stability criterion with less variables for time-delay systems

Slack variables approach is an important technique for tackling the delay-dependent stability problem for systems with time-varying delay. In this paper, a new delay-dependent stability criterion is presented without introducing any slack variable. The technique is based on a simply integral inequality. The result is shown to be equivalent to some existing ones but includes the least number of variables. Thus, redundant selection and computation can be avoided so that the computational burden can be largely reduced. Numerical examples are given to illustrate the effectiveness of the proposed stability conditions. Recommended by Editorial Board member Young Soo Suh under the direction of Editor Jae Weon Choi. The authors would like to thank the Associate Editor and the Reviewers for their very helpful comments and suggestions. This work was supported in part by the Funds for Creative Research Groups of China under Grant 60821063, by the State Key Program of National Natural Science of China under Grant 60534010, by the Funds of National Science of China under Grant 60674021, 60774013, 60774047, National 973 Program of China under Grant No. 2009CB320604, and by the Funds of Ph.D. program of MOE, China under Grant 20060145019 and the 111 Project B08015. Xun-Lin Zhu received the B.S. degree in Applied Mathematics from Information Engineering Institute, Zhengzhou, China, in 1986, the M.S. degree in basic mathematics from Zhengzhou University, Zhengzhou, China, in 1989, and the Ph.D. degree in Control Theory and Engineer-ing from Northeastern University, Shenyang, China, in 2008. Currently, he is an Associate Professor at Zhengzhou University of Light Industry, Zhengzhou, China. His research interests include neural networks and networked control systems. Guang-Hong Yang received the B.S. and M.S. degrees in Northeast University of Technology, China, in 1983 and 1986, respectively, and the Ph.D. degree in Control Engineering from Northeastern University, China (formerly, Northeast University of Technology), in 1994. He was a Lecturer/Associate Professor with Northeastern University from 1986 to 1995. He joined the Nanyang Technological University in 1996 as a Postdoctoral Fellow. From 2001 to 2005, he was a Research Scientist/Senior Research Scientist with the National University of Singapore. He is currently a Professor at the College of Information Science and Engineering, Northeastern University. His current research interests include fault-tolerant control, fault detection and isolation, non-fragile control systems design, and robust control. Dr. Yang is an Associate Editor for the International Journal of Control, Automation, and Systems (IJCAS), and an Associate Editor of the Conference Editorial Board of the IEEE Control Systems Society. Tao Li was born in 1979. He is now pursuing a Ph.D. degree in Research Institute of Automation Southeast University, China. His current research interests include time-delay systems, neural networks, robust control, fault detection and diagnosis. Chong Lin received the B.Sci and M.Sci in Applied Mathematics from the Northeastern University, China, in 1989 and 1992, respectively, and the Ph.D in Electrical and Electronic Engineering from the Nanyang Technological University, Singapore, in 1999. He was a Research Associate with the University of Hong Kong in 1999. From 2000 to 2006, he was a Research Fellow with the National University of Singapore. He is currently a Profesor with the Institute of Complexity Science, Qingdao University, China. His current research interests are mainly in the area of systems analysis and control. Lei Guo was born in 1966. He received the Ph.D. degree in Control Engineering from Southeast University (SEU), PR China, in 1997. From 1999 to 2004, he has worked at Hong Kong University, IRCCyN (France), Glasgow University, Loughborough University and UMIST, UK. Now he is a Professor in School of Instrument Science and Opto-Electronics Engineering, Beihang University. He also holds a Visiting Professor position in the University of Manchester, UK and an invitation fellowship in Okayama University, Japan. His research interests include robust control, stochastic systems, fault detection, filter design, and nonlinear control with their applications.     

Program transformation system based on generalized partial computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works. Yoshihiko Futamura, Ph.D.: He is Professor of Department of Information and Computer Science and the director of the Institute for Software Production Technology (ISPT) of Waseda University. He received his BS in mathematics from Hokkaido University in 1965, MS in applied mathematics from Harvard University in 1972 and Ph.D. degree from Hokkaido University in 1985. He joined Hitachi Central Research Laboratory in 1965 and moved to Waseda University in 1991. He was a visiting professor of Uppsala University from 1985 to 1986 and a visiting scholar of Harvard University from 1988 to 1989. Automatic generation of computer programs and programming methodology are his main research fields. He is the inventor of the Futamura Projections in partial evaluation and ISO8631 PAD (Problem Analysis Diagram). Zenjiro Konishi: He is a visiting lecturer of Institute for Software Production Technology, Waseda University. He received his M. Sc. degree in mathematics from Waseda University in 1995. His research interests include automated theorem proving. He received JSSST Takahashi Award in 2001. He is a member of JSSST and IPSJ. Robert Glück, Ph.D., Habil.: He is an Associate Professor of Computer Science at the University of Copenhagen. He received his Ph.D. and Habilitation (venia docendi) from the Vienna University of Technology in 1991 and 1997. He was research assistant at the City University of New York and received twice the Erwin-Schrodinger-Fellowship of the Austrian Science Foundation (FWF). After being an Invited Fellow of the Japan Society for the Promotion of Science (JSPS), he is now funded by the PRESTO21 program for basic research of the Japan Science and Technology Corporation (JST) and located at Waseda University in Tokyo. His main research interests are advanced programming languages, theory and practice of program transformation, and metaprogramming.     

Relative positioning for team robot navigation

The research presented in this paper approaches the issue of robot team navigation using relative positioning. With this approach each robot is equipped with sensors that allow it to independently estimate the relative direction of an assigned leader. Acoustic sensor systems are used and were seen to work very effectively in environments where datum relative positioning systems (such as GPS or acoustic transponders) are typically ineffective. While acoustic sensors provide distinct advantages, the variability of the acoustic environment presents significant control challenges. To address this challenge, directional control of the robot was accomplished with a feed forward neural network trained using a genetic algorithm, and a new approach to training using recent memories was successfully implemented. The design of this controller is presented and its performance is compared with more traditional classic logic and behavior controllers. Patrick McDowell received his bachelor's degree in Computer Science in 1984 from the University of Idaho. He spent the next 15 years working as a computer scientist for a small defense contractor where he specialized in real time data acquisition, application development, and image processing. In 1999 he received his master's degree in computer science from the University of Southern Mississippi. In 2000 he began work at the Naval Research Lab where he has focused on application of machine learning techniques to autonomous underwater navigation. In 2005 he received his Ph.D. in Computer Science from Louisiana State University. His research interests include legged robotics, machine learning, and artificial intelligence. In Fall of 2006 he joined Southeastern Louisiana University as an assistant professor of Computer Science. Brian S. Bourgeois received his Ph.D. in Electrical Engineering from Tulane University located in New Orleans, LA in 1991. Since then he has worked at the Stennis Space Center, MS detachment of the Naval Research Laboratory. He has worked on research projects spanning an array of technologies including airborne survey sytems, acoustic backscattering, bathymetry and imaging sonar systems, the ORCA unmanned underwater vehicle and the development of an autonomous survey system for hydrographic survey ships. He is presently the head of the Position, Navigation and Timing team at NRL with research interests including underwater positioning and communications and autonomous navigation. Ms. McDowell received her M.S. in Applied Physics in 2002 from the University or New Orleans. She is presently a candidate for a Ph. D. in Engineering and Applied Science. She joined the Naval Research Laboratory in 1991 as a research engineer and has spent most of that time working in experimental and theoretical acoustic modeling. Ms. McDowell's specific research interest lie in the areas of sonar performance analysis. Dr. S. S. Iyengar is the Chairman and Roy Paul Daniels Chaired Professor of Computer Science at Louisiana State University and is also Satish Dhawan Chaired Professor at Indian Institute of Science. He has been involved with research in high-performance algorithms, data structures, sensor fusion, data mining, and intelligent systems since receiving his Ph.D. degree (1974) and his M.S. from the Indian Institute of Science (1970). He has been a consultant to several industrial and government organizations (JPL, NASA etc.). In 1999, Professor Iyengar won the most prestigious research award titled Distinguished Research Award and a university medal for his research contributions in optimal algorithms for sensor fusion/image processing. Dr. Jianhua Chen received her Ph.D. in computer science in 1988 from Jilin University, Chang Chun, China. In August 1988, She joined the Computer Science Department of Louisiana State University, Baton Rouge, USA, where she is currently an associate professor. Dr. Chen's research interests include Machine Learning and Data Mining, Fuzzy Sets and Systems, Knowledge Representation and Reasoning.     

Fast evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm.     

Fast multicast on multistage interconnection networks using multi-head worms

1IntroductionMulticastcommunication,whichreferstothedeliveryofamessagefromasinglesourcenodetoanumberofdestinationnodes,isfrequentlyusedindistributed-memoryparallelcomputersystemsandnetworks[1].Efficientimplementationofmulticastcommunicationiscriticaltotheperformanceofmessage-basedscalableparallelcomputersandswitch-basedhighspeednetworks.Switch-basednetworksorindirectnetworks,basedonsomevariationsofmultistageiDterconnectionnetworks(MINs),haveemergedasapromisingnetworkajrchitectureforconstruct…     

A-SATCHMORE: SATCHMORE with availability checking

We present an improvement of SATCHMORE, calledA-SATCHMORE, by incorporating availability checking into relevancy. Because some atoms unavailable to the further computation are also marked relevant, SATCHMORE suffers from a potential explosion of the search space. Addressing this weakness of SATCHMORE, we show that an atom does not need to be marked relevant unless it is available to the further computation and no non-Horn clause needs to be selected unless all its consequent atoms are marked availably relevant, i.e., unless it is totally availably relevant. In this way,A-SATCHMORE is able to further restrict the ues of non-Horn clauses (therefore to reduce the search space) and makes the proof more goal-oriented. Our theorem prover,A-SATCHMORE, can be simply implemented in PROLOG based on SATCHMORE. We discuss how to incorporate availability cheeking into relevancy, describe our improvement and present the implementation. We also prove that our theorem prover is sound and complete, and provide examples to show the power of our availability approach. This research is supported in part by the Japanese Ministry of Education and the Artificial Intelligence Research Promotion Foundation. Lifeng He, Ph.D: He received the B. E. degree from Northwest Institute of Light Industry, China, in 1982, the M. S. and Ph.D. degrees in AI and computer science from Nagoya Institute of Technology, Japan, in 1994 and 1997, respectively. He currently works at the Institute of Open System in Nagoya, Japan. His research interests include automated reasoning, theorem proving, logic programming, knowledge bases, multi-agent cooperation and modal logic. Yuyan Chao, M. S.: She received the B. E. degree from Northwest Institute of Light Industry, China, in 1984, and the M. S. degree from Nagoya University, Japan, in 1997. She is currently a doctoral candidate in the Department of Human Information, Nagoya University. Her research interests include image processing, graphic understanding, CAD and theorem proving. Yuka Shimajiri, M. S.: She currently works as a Assistant Professor in Department of Artificial Intelligence and Computer Science at the Nagoya Institute of Technology. She received her B.Eng. and M.Eng. from the Nagoya Institute of Technology in 1994 and 1996, respectively. Her current research interests include logic programming and automated deduction. She is a member of IPSJ and JSAI. Hirohisa Seki, Ph.D.: He received the B. E., M. E. and Ph.D degrees from the University of Tokyo in 1979, 1981 and 1991 respectively. He joined the Central Research Laboratory of Mitsubishi Electric Corporation in 1981. From 1985 to 1989, he was with the Institute for New Generation Computer Technology (ICOT). Since 1992, he has been an Associate Professor in the Department of AI and Computer Science at Nagoya Institute of Technology. His current research interests include logic programming, deductive databases and automated deduction. He is a member of ACM, IEEE, IPSJ and JSAI. Hidenori Itoh, Ph.D.: He received the B. S. degree from Fukui University, in 1969, the M. S. degree and Ph.D degree from Nagoya University, Japan, in 1971 and 1974, respectively. From 1974 to 1985, he worked at Nippon Telephone and Telegraph Laboratories, developing operating systems. From 1985 to 1989, he was with the Institute for New Generation Computer Technology, developing knowledge base systems. Since 1989, he has become a professor at the Nagoya Institute of Technology. His current research interests include image processing, parallel computing, fuzzy logic and knowledge processing.