Static extensivity analysis for λ-definable functions over lattices

We employ a static analysis to examine the extensivity (∀x:x≤f(x)) of functions defined over lattices in a λ-calculus augmented with lattice operations. The need for such a verification procedure has arisen in our work on a generator system (called Zoo) of static program-analyzers. The input to Zoo is a static analysis specification that consists of lattice definitions and function definitions over the lattices. Once the extensivity of the functions is ascertained, the generated analyzer is guaranteed to terminate when the lattices have finite-heights. The extensivity analysis consists of a sound syntax-driven deductive rules whose satisfiability check is done by a constraint solving procedure. Hyunjun Eo: He is a Ph.D. candidate of Computer Science Dept. at KAIST (Korea Advanced Institute of Science and Technology). He received his B.S. and M.S. in Computer Science from KAIST in 1996 and 1998, respectively. For 1998–2003, he was a research assistant of the National Creative Research Initiative Center for Research On Program Analysis System. His research interest has been on static program analysis, program logics, and higher-order and typed languages. He is currently working on developing a tool for automatic generation of program analyzers. Kwangkeun Yi, Ph.D.: His research interest has been on semantic-based program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995–2003, he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since Fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University. Kwang-Moo Choe, Ph.D.: He is a professor of Computer Science at Korea Advanced Institute of Science and Technology. He received his B.S. from Seoul National University in 1976, and his M.S. and Ph.D. from Korea Advanced Institute of Science and Technology in 1978 and 1984, respectively. For 1985–1986, he was a technical staff of AT&T Bell Labs at Murray Hill. His research interest is formal language theory, parallel evaluation of logic programs, and optimizing compilers.     

The narrowing-driven approach to functional logic program specialization

Partial evaluation is a semantics-based program optimization technique which has been investigated within different programming paradigms and applied to a wide variety of languages. Recently, a partial evaluation framework for functional logic programs has been proposed. In this framework, narrowing—the standard operational semantics of integrated languages—is used to drive the partial evaluation process. This paper surveys the essentials of narrowing-driven partial evaluation. Elvira Albert, Ph.D.: She is an associate professor in Computer Science at the Technical University of Valencia, Spain. She received her bachelors degree in computer science in 1998 and her Ph.D. in computer science in 2001, both from the Technical University of Valencia. She has investigated on program optimization and on partial evaluation for declarative multi-paradigm programming languages. Her current research interests include term rewriting, multi-paradigm declarative programming, and formal methods, in particular semantics-based program analysis, transformation, specification, verification, and debugging. Germán Vidal, Ph.D.: He is an associate professor in Computer Science at the Technical University of Valencia, Spain. He obtained his bachelors degree in computer science in 1992 and his Ph.D. in computer science in 1996, both from the Technical University of Valencia. He is active on several research topics in Functional Logic Programming. He has worked on compositionality, on abstract interpretation, and on program transformation techniques for functional logic programs. Currently, his research interests include declarative multi-paradigm programming languages, term rewriting, and semantics-based program manipulation, in particular partial evaluation.     

Proofs of a set of hybrid let-polymorphic type inference algorithms

We present a generalized let-polymorphic type inference algorithm, prove that any of its instances is sound and complete with respect to the Hindley/Milner let-polymorphic type system, and find a condition on two instance algorithms so that one algorithm should find type errors earlier than the other. By instantiating the generalized algorithm with different parameters, we can obtain not only the two opposite algorithms (the bottom-up standard algorithmW and the top-down algorithmM) but also other hybrid algorithms which are used in real compilers. Such instances’ soudness and completeness follow automatically, and their relative earliness in detecting type-errors is determined by checking a simple condition. The set of instances of the generalized algorithm is a superset of those used in the two most popular ML compilers: SML/NJ and OCaml. This work is supported by Creative Research Initiatives of the Korean Ministry of Science and Technology National Creative Research Initiative Center, http://ropas.kaist.ac.kr Work done while the third author was associated with Korea Advanced Institute of Science and Technology Hyunjun Eo: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He recieved his bachelor’s degree and master’s degree in Computer Science from KAIST in 1996 and 1998, respectively. His research interest has been on static program analysis, fixpoint iteration algorithm and higher-order and typed languages. From fall 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on developing a tool for automatic generation of program analyzer. Oukseh Lee: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He received his bachelor’s and master’s degree in Computer Science from KAIST in 1995 and 1997, respectively. His research interest has been on static program analysis, type system, program language implementation, higher-order and typed languages, and program verification. From 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on compile-time analyses and verification for the memory behavior of programs. Kwangkeun Yi, Ph.D.: His research interest has been on semanticbased program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995 to 2003 he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University.     

Behavioural notions for elementary net systems

We study the relationships between a number of behavioural notions that have arisen in the theory of distributed computing. In order to sharpen the under-standing of these relationships we apply the chosen behavioural notions to a basic net-theoretic model of distributed systems called elementary net systems. The behavioural notions that are considered here are trace languages, non-sequential processes, unfoldings and event structures. The relationships between these notions are brought out in the process of establishing that for each elementary net system, the trace language representation of its behaviour agrees in a strong way with the event structure representation of its behaviour. M. Nielsen received a Master of Science degree in mathematics and computer science in 1973, and a Ph.D. degree in computer science in 1976 both from Aarhus University, Denmark. He has held academic positions at Department of Computer Science, Aarhus University, Denmark since 1976, and was visiting researcher at Computer Science Department, University of Edinburgh, U.K., 1977–79, and Computer Laboratory, Cambridge University, U.K., 1986. His research interest is in the theory of distributed computing. Grzegorz Rozenberg received a master of engineering degree from the Department of Electronics (section computers) of the Technical University of Warsaw in 1964 and a Ph.D. in mathematics from the Institute of Mathematics of the Polish Academy of Science in 1968. He has held acdeemic positions at the Institute of Mathematics of the Polish Academy of Science, the Department of Mathematics of Utrecht University, the Department of Computer Science at SUNY at Buffalo, and the Department of Mathematics of the University of Antwerp. He is currently Professor at the Department of Computer Science of Leiden University and Adjoint Professor at the Department of Computer Science of the University of Colorado at Boulder. His research interests include formal languages and automata theory, theory of graph transformations, and theory of concurrent systems. He is currently President of the European Association for Theoretical Computer Science (EATCS). P.S. Thiagarajan received the Bachelor of Technology degree from the Indian Institute of Technology, Madras, India in 1970. He was awarded the Ph.D. degree by Rice University, Houston Texas, U.S.A, in 1973. He has been a Research Associate at the Massachusetts Institute of Technology, Cambridge a Staff Scientist at the Geosellschaft für Mathematik und Datenverarbeitung, St. Augustin, a Lektor at Århus University, Århus and an Associate Professor at the Institute of Mathematical Sciences, Madras. He is currently a Professor at the School of Mathematics, SPIC Science Foundation, Madras. He research intest is in the theory of distributed computing.     

Segmentation of stick text based on sub connected area analysis

A new stick text segmentation method based on the sub connected area analysis is introduced in this paper.The foundation of this method is the sub connected area representation of text image that can represent all connected areas in an image efficiently.This method consists mainly of four steps:sub connected area classification,finding initial boundary following point,finding optimal segmentation point by boundary tracing,and text segmentaton.This method is similar to boundary analysis method but is more efficient than boundary analysis.     

Block cipher based on reversible cellular automata

We propose a new encryption algorithm relying on reversible cellular automata (CA). The behavior complexity of CA and their parallel nature makes them interesting candidates for cryptography. The proposed algorithm belongs to the class of symmetric key systems. Marcin Seredynski: He is a Ph.D. student at University of Luxembourg and Polish Academy of Sciences. He received his M.S. in 2004 from Faculty of Electronics and Information Technology in Warsaw University of Technology. His research interests include cryptography, cellular automata, nature inspired algorithms and network security. Currently he is working on intrusion detection algorithms for ad-hoc networks. Pascal Bouvry, Ph.D.: He earned his undergraduate degree in Economical & Social Sciences and his Master degree in Computer Science with distinction (’91) from the University of Namur, Belgium. He went on to obtain his Ph.D. degree (’94) in Computer Science with great distinction at the University of Grenoble (INPG), France. His research at the IMAG laboratory focussed on Mapping and scheduling task graphs onto Distributed Memory Parallel Computers. Next, he performed post-doctoral researches on coordination languages and multi-agent evolutionary computing at CWI in Amsterdam. He gained industrial experience as manager of the technology consultant team for FICS in the banking sector (Brussels, Belgium). Next, he worked as CEO and CTO of SDC (Ho Chi Minh city, Vietnam) in the telecom, semi-conductor and space industry. After that, He moved to Montreal Canada as VP Production of Lat45 and Development Director for MetaSolv Software in the telecom industry. He is currently serving as Professor in the group of Computer Science and Communications (CSC) of the Faculty of Sciences, Technology and Communications of Luxembourg University and he is heading the Intelligent & Adaptive Systems lab. His current research interests include: ad-hoc networks & grid-computing, evolutionary algorithms and multi-agent systems.     

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.     

Some impossibility results in interprocess synchronization

Summary In this paper we construct a formal specification of the problem of synchronizing asynchronous processes under strong fairness. We prove that strong interaction fairness is impossible for binary (and hence for multiway) interactions and strong process fairness is impossible for multiway interactions. Yih-Kuen Tsay received his B.S. degree form National Taiwan University in 1984 and his M.S. degree from UCLA in 1989. He is currently a Ph.D. candidate in the UCLA Computer Science Department. His research interests include distributed algorithms, fault-tolerant systems, and specification and verification of concurrent programs. Rajive L. Bagrodia received the B. Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay in 1981 and the M.A. and Ph.D. degrees in Computer Science from the University of Texas at Austin in 1983 and 1987 respectively. He is currently an Assistant Professor in the Computer Science Department at UCLA. His research interests include parallel languages, distributed algorithms, parallel simulation and software design methodologies. He was selected as a 1991 Presidential Young Investigator by NSF.This research was partially supported by NSF PYI Award number ASC9157610 and by ONR under grant N00014-91-J1605     

Constructive negation and constraint logic programming with sets

The aim of this paper is to extend theConstructive Negation technique to the case ofCLP(SεT), a Constraint Logic Programming (CLP) language based on hereditarily (and hybrid) finite sets. The challenging aspects of the problem originate from the fact that the structure on whichCLP(SεT) is based is notadmissible closed, and this does not allow to reuse the results presented in the literature concerning the relationships betweenCLP and constructive negation. We propose a new constraint satisfaction algorithm, capable of correctly handling constructive negation for large classes ofCLP(SεT) programs; we also provide a syntactic characterization of such classes of programs. The resulting algorithm provides a novel constraint simplification procedure to handle constructive negation, suitable to theories where unification admits multiple most general unifiers. We also show, using a general result, that it is impossible to construct an interpreter forCLP(SεT) with constructive negation which is guaranteed to work for any arbitrary program; we identify classes of programs for which the implementation of the constructive negation technique is feasible. Agostino Dovier, Ph.D.: He is a researcher in the Department of Science and Technology at the University of Verona, Italy. He obtained his master degree in Computer Science from the University of Udine, Italy, in 1991 and his Ph.D. in Computer Science from the University of Pisa, Italy, in 1996. His research interests are in Programming Languages and Constraints over complex domains, such as Sets and Multisets. He has published over 20 research papers in International Journals and Conferences. He is teaching a course entitled “Special Languages and Techniques for Programming” at the University of Verona. Enrico Pontelli, Ph.D.: He is an Assistant Professor in the Department of Computer Science at the New Mexico State University. He obtained his Laurea degree from the University of Udine (Italy) in 1991, his Master degree from the University of Houston in 1992, and his Ph.D. degree from New Mexico State University in 1997. His research interests are in Programming Languages, Parallel Processing, and Constraint Programming. He has published over 50 papers and served on the program committees of different conferences. He is presently the Associate Director of the Laboratory for Logic, Databases, and Advanced Programming. Gianfranco Rossi, Ph.D.: He received his degree in Computer Science from the University of Pisa in 1979. From 1981 to 1983 he was employed at Intecs Co. System House in Pisa. From November 1983 to February 1989 he was a researcher at the Dipartimento di Informatica of the University of Turin. Since March 1989 he is an Associate Professor of Computer Science, currently with the University of Parma. He is the author of several papers dealing mainly with programming languages, in particular logic programming languages and Prolog, and extended unification algorithms. His current research interests are (logic) programming languages with sets and set unification algorithms.     

Learning Horn definitions: Theory and an application to planning

A Horn definition is a set of Horn clauses with the same predicate in all head literals. In this paper, we consider learning non-recursive, first-order Horn definitions from entailment. We show that this class is exactly learnable from equivalence and membership queries. It follows then that this class is PAC learnable using examples and membership queries. Finally, we apply our results to learning control knowledge for efficient planning in the form of goal-decomposition rules. Chandra Reddy, Ph.D.: He is currently a doctoral student in the Department of Computer Science at Oregon State University. He is completing his Ph.D. on June 30, 1998. His dissertation is entitled “Learning Hierarchical Decomposition Rules for Planning: An Inductive Logic Programming Approach.” Earlier, he had an M. Tech in Artificial Intelligence and Robotics from University of Hyderabad, India, and an M.Sc.(tech) in Computer Science from Birla Institute of Technology and Science, India. His current research interests broadly fall under machine learning and planning/scheduling—more specifically, inductive logic programming, speedup learning, data mining, and hierarchical planning and optimization. Prasad Tadepalli, Ph.D.: He has an M.Tech in Computer Science from Indian Institute of Technology, Madras, India and a Ph.D. from Rutgers University, New Brunswick, USA. He joined Oregon State University, Corvallis, as an assistant professor in 1989. He is now an associate professor in the Department of Computer Science of Oregon State University. His main area of research is machine learning, including reinforcement learning, inductive logic programming, and computational learning theory, with applications to classification, planning, scheduling, manufacturing, and information retrieval.     

Aggregation and negation-as-failure

Set-grouping and aggregation are powerful operations of practical interest in database query languages. An aggregate operation is a function that maps a set to some value, e.g., the maximum or minimum in the set, the cardinality of this set, the summation of all its members, etc. Since aggregate operations are typically non-monotonic in nature, recursive programs making use of aggregate operations must be suitably restricted in order that they have a well-defined meaning. In a recent paper we showed that partial-order clauses provide a well-structured means of formulating aggregate operations with recursion. In this paper, we consider the problem of expressing partial-order programs via negation-as-failure (NF), a well-known non-monotonic operation in logic programming. We show a natural translation of partial-order programs to normal logic programs: Anycost-monotonic partial-order programsP is translated to astratified normal program such that the declarative semantics ofP is defined as the stratified semantics of the translated program. The ability to effect such a translation is significant because the resulting normal programs do not make any explicit use of theaggregation capability, yet they are concise and intuitive. The success of this translation is due to the fact that the translated program is a stratified normal program. That would not be the case for other more general classes of programs thancost-monotonic partial-order programs. We therefore develop in stages a refined translation scheme that does not require the translated programs to be stratified, but requires the use of a suitable semantics. The class of normal programs originating from this refined translation scheme is itself interesting: Every program in this class has a clear intended total model, although these programs are in general neither stratified nor call-consistent, and do not have a stable model. The partial model given by the well-founded semantics is consistent with the intended total model and the extended well founded semantics,WFS ⁺, defines the intended model. Since there is a well-defined and efficient operational semantics for partial-order programs^{14, 15, 21)} we conclude that the gap between expression of a problem and computing its solution can be reduced with the right level of notation. Mauricio J. Osorio G., Ph.D.: He is an Associate Professor in the Department of Computer Systems Engineering, University of the Americas, Puebla, Mexico. He is the Head of the Laboratory of Theoretical Computer Science of the Center of Research (CENTIA), Puebla, Mexico. His research is currently funded by CENTIA and CONACYT (Ref. #C065-E9605). He is interested in Applications of Logic to Computer Science, with special emphasis on Logic Programming. He received his B.Sc. in Computer Science from the Universidad Autonoma de Puebla, his M.Sc. in Electrical Engineering from CINVESTAV in Mexico, and his Ph.D. from the State University of New York at Buffalo in 1995. Bharat Jayaraman, Ph.D.: He is an Associate Professor in the Department of Computer Science at the State University of New York at Buffalo. He obtained his bachelors degree in Electronics from the Indian Institute of Technology, Madras in 1975, and his Ph.D. from the University of Utah in 1981. His research interests are in Programming Languages and Declarative Modeling of Complex Systems. He has published over 50 research papers. He has served on the program committees of several conferences in the area of Programming Languages, and he is presently on the Editorial Board of the Journal of Functional and Logic Programming.     

Learning with globally predictive tests

We introduce a new bias for rule learning systems. The bias only allows a rule learner to create a rule that predicts class membership if each test of the rule in isolation is predictive of that class. Although the primary motivation for the bias is to improve the understandability of rules, we show that it also improves the accuracy of learned models on a number of problems. We also introduce a related preference bias that allows creating rules that violate this restriction if they are statistically significantly better than alternative rules without such violations. Michael J. Pazzani, Ph.D.: He is a Full Professor and Chair in the Department of Information and Computer Science at the University of California, Irvine. He obtained his bachelors degree from the University of Connecticut in 1980 and his Ph. D. from University of California, Los Angles in 1987. His research interests are in machine learning, cognitive modeling and information access. He has published over 100 research papers and 2 books. He has served on the Editorial Board of the Machine Learning and the Journal of Artificial Intelligence Research.     

Preference update for e-commerce applications: Model,language, and processing

It is likely that customers issue requests based on out-of-date information in e-commerce application systems. Hence, the transaction failure rates would increase greatly. In this paper, we present a preference update model to address this problem. A preference update is an extended SQL update statement where a user can request the desired number of target data items by specifying multiple preferences. Moreover, the preference update allows easy extraction of criteria from a set of concurrent requests and, hence, optimal decisions for the data assignments can be made. We propose a group evaluation strategy for preference update processing in a multidatabase environment. The experimental results show that the group evaluation can effectively increase the customer satisfaction level with acceptable cost. Peng Li is the Chief Software Architect of didiom LLC. Before that, he was a visiting assistant professor of computer science department in Western Kentucky University. He received his Ph.D. degree of computer science from the University of Texas at Dallas. He also holds a B.Sc. and M.S. in Computer Science from the Renmin University of China. His research interests include database systems, database security, transaction processing, distributed and Internet computer and E-commerce. Manghui Tu received a Bachelor degree of Science from Wuhan University, P.R. China in 1996, and a Master Degree in Computer Science from the University of Texas at Dallas 2001. He is currently working toward the PhD degree in the Department of Computer Science at the University of Texas at Dallas. Mr. Tu’s research interests include distributed systems, grid computing, information security, mobile computing, and scientific computing. His PhD research work focus on the data management in secure and high performance data grid. He is a student member of the IEEE. I-Ling Yen received her BS degree from Tsing-Hua University, Taiwan, and her MS and PhD degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at the University of Texas at Dallas. Dr. Yen’s research interests include fault-tolerant computing, security systems and algorithms, distributed systems, Internet technologies, E-commerce, and self-stabilizing systems. She had published over 100 technical papers in these research areas and received many research awards from NSF, DOD, NASA, and several industry companies. She has served as Program Committee member for many conferences and Program Chair/Co-Chair for the IEEE Symposium on Application-Specific Software and System Engineering & Technology, IEEE High Assurance Systems Engineering Symposium, IEEE International Computer Software and Applications Conference, and IEEE International Symposium on Autonomous Decentralized Systems. She is a member of the IEEE. Zhonghang Xia received the B.S. degree in applied mathematics from Dalian University of Technology in 1990, the M.S. degree in Operations Research from Qufu Normal University in 1993, and the Ph.D. degree in computer science from the University of Texas at Dallas in 2004. He is now an assistant professor in the Department of Computer Science, Western Kentucky University, Bowling Green, KY. His research interests are in the area of multimedia computing and networking, distributed systems, and data mining.     

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.     

S-Club: an overlay-based efficient service discovery mechanism in CROWN Grid

Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing Grid Information Service (GIS) mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in our CROWN Grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches. Chunming Hu is a research staff in the Institute of Advanced Computing Technology at the School of Computer Science and Engineering, Beihang University, Beijing, China. He received his B.E. and M.E. in Department of Computer Science and Engineering in Beihang University. He received the Ph.D. degree in School of Computer Science and Engineering of Beihang University, Beijing, China, 2005. His research interests include peer-to-peer and grid computing; distributed systems and software architectures. Yanmin Zhu is a Ph.D. candidate in the Department of Computer Science, Hong Kong University of Science and Technology. He received his B.S. degree in computer science from Xi’an Jiaotong University, Xi’an, China, in 2002. His research interests include grid computing, peer-to-peer networking, pervasive computing and sensor networks. He is a member of the IEEE and the IEEE Computer Society. Jinpeng Huai is a Professor and Vice President of Beihang University. He serves on the Steering Committee for Advanced Computing Technology Subject, the National High-Tech Program (863) as Chief Scientist. He is a member of the Consulting Committee of the Central Government’s Information Office, and Chairman of the Expert Committee in both the National e-Government Engineering Taskforce and the National e-Government Standard office. Dr. Huai and his colleagues are leading the key projects in e-Science of the National Science Foundation of China (NSFC) and Sino-UK. He has authored over 100 papers. His research interests include middleware, peer-to-peer (P2P), grid computing, trustworthiness and security. Yunhao Liu received his B.S. degree in Automation Department from Tsinghua University, China, in 1995, and an M.A. degree in Beijing Foreign Studies University, China, in 1997, and an M.S. and a Ph.D. degree in computer science and engineering at Michigan State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science and Engineering at Hong Kong University of Science and Technology. His research interests include peer-to-peer computing, pervasive computing, distributed systems, network security, grid computing, and high-speed networking. He is a senior member of the IEEE Computer Society. Lionel M. Ni is chair professor and head of the Computer Science and Engineering Department at Hong Kong University of Science and Technology. Lionel M. Ni received the Ph.D. degree in electrical and computer engineering from Purdue University, West Lafayette, Indiana, in 1980. He was a professor of computer science and engineering at Michigan State University from 1981 to 2003, where he received the Distinguished Faculty Award in 1994. His research interests include parallel architectures, distributed systems, high-speed networks, and pervasive computing. A fellow of the IEEE and the IEEE Computer Society, he has chaired many professional conferences and has received a number of awards for authoring outstanding papers.     

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.     

Efficient algorithms for optimistic crash recovery

Summary Recovery from transient processor failures can be achieved by using optimistic message logging and checkpointing. The faulty processorsroll back, and some/all of the non-faulty processors also may have to roll back. This paper formulates the rollback problem as a closure problem. A centralized closure algorithm is presented together with two efficient distributed implementations. Several related problems are also considered and distributed algorithms are presented for solving them. S. Venkatesan received the B. Tech. and M. Tech degrees from the Indian Institute of Technology, Madras in 1981 and 1983, respectively and the M.S. and Ph.D. degrees in Computer Science from the University of Pittsburgh in 1985 and 1988. He joined the University of Texas at Dallas in January 1989, where he is currently an Assistant Professor of Computer Science. His research interests are in fault-tolerant distributed systems, distributed algorithms, testing and debugging distributed programs, fault-tolerant telecommunication networks, and mobile computing. Tony Tony-Ying Juang is an Associate Professor of Computer Science at the Chung-Hwa Polytechnic Institute. He received the B.S. degree in Naval Architecture from the National Taiwan University in 1983 and his M.S. and Ph.D. degrees in Computer Science from the University of Texas at Dallas in 1989 and 1992, respectively. His research interests include distributed algorithms, fault-tolerant distributed computing, distributed operating systems and computer communications.This research was supported in part by NSF under Grant No. CCR-9110177 and by the Texas Advanced Technology Program under Grant No. 9741-036     

Using discriminant analysis for multi-class classification: an experimental investigation

Many supervised machine learning tasks can be cast as multi-class classification problems. Support vector machines (SVMs) excel at binary classification problems, but the elegant theory behind large-margin hyperplane cannot be easily extended to their multi-class counterparts. On the other hand, it was shown that the decision hyperplanes for binary classification obtained by SVMs are equivalent to the solutions obtained by Fisher's linear discriminant on the set of support vectors. Discriminant analysis approaches are well known to learn discriminative feature transformations in the statistical pattern recognition literature and can be easily extend to multi-class cases. The use of discriminant analysis, however, has not been fully experimented in the data mining literature. In this paper, we explore the use of discriminant analysis for multi-class classification problems. We evaluate the performance of discriminant analysis on a large collection of benchmark datasets and investigate its usage in text categorization. Our experiments suggest that discriminant analysis provides a fast, efficient yet accurate alternative for general multi-class classification problems. Tao Li is currently an assistant professor in the School of Computer Science at Florida International University. He received his Ph.D. degree in Computer Science from University of Rochester in 2004. His primary research interests are: data mining, machine learning, bioinformatics, and music information retrieval. Shenghuo Zhu is currently a researcher in NEC Laboratories America, Inc. He received his B.E. from Zhejiang University in 1994, B.E. from Tsinghua University in 1997, and Ph.D degree in Computer Science from University of Rochester in 2003. His primary research interests include information retrieval, machine learning, and data mining. Mitsunori Ogihara received a Ph.D. in Information Sciences at Tokyo Institute of Technology in 1993. He is currently Professor and Chair of the Department of Computer Science at the University of Rochester. His primary research interests are data mining, computational complexity, and molecular computation.     

Adaptive solutions to the mutual exclusion problem

Summary Algorithms for mutual exclusion that adapt to the current degree of contention are developed. Afilter and a leader election algorithm form the basic building blocks. The algorithms achieve system response times that are independent of the total number of processes and governed instead by the current degree of contention. The final algorithm achieves a constant amortized system response time. Manhoi Choy was born in 1967 in Hong Kong. He received his B.Sc. in Electrical and Electronic Engineerings from the University of Hong Kong in 1989, and his M.Sc. in Computer Science from the University of California at Santa Barbara in 1991. Currently, he is working on his Ph.D. in Computer Science at the University of California at Santa Barbara. His research interests are in the areas of parallel and distributed systems, and distributed algorithms. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B.Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.A preliminary version of the paper appeared in the 12th Annual ACM Symposium on Principles of Distributed ComputingWork supported in part by NSF grants CCR-9008628 and CCR-9223094     

XCQ: A queriable XML compression system

XML has already become the de facto standard for specifying and exchanging data on the Web. However, XML is by nature verbose and thus XML documents are usually large in size, a factor that hinders its practical usage, since it substantially increases the costs of storing, processing, and exchanging data. In order to tackle this problem, many XML-specific compression systems, such as XMill, XGrind, XMLPPM, and Millau, have recently been proposed. However, these systems usually suffer from the following two inadequacies: They either sacrifice performance in terms of compression ratio and execution time in order to support a limited range of queries, or perform full decompression prior to processing queries over compressed documents.In this paper, we address the above problems by exploiting the information provided by a Document Type Definition (DTD) associated with an XML document. We show that a DTD is able to facilitate better compression as well as generate more usable compressed data to support querying. We present the architecture of the XCQ, which is a compression and querying tool for handling XML data. XCQ is based on a novel technique we have developed called DTD Tree and SAX Event Stream Parsing (DSP). The documents compressed by XCQ are stored in Partitioned Path-Based Grouping (PPG) data streams, which are equipped with a Block Statistics Signature (BSS) indexing scheme. The indexed PPG data streams support the processing of XML queries that involve selection and aggregation, without the need for full decompression. In order to study the compression performance of XCQ, we carry out comprehensive experiments over a set of XML benchmark datasets. Wilfred Ng obtained his M.Sc.(Distinction) and Ph.D. degrees from the University of London. His research interests are in the areas of databases and information Systems, which include XML data, database query languages, web data management, and data mining. He is now an assistant professor in the Department of Computer Science, the Hong Kong University of Science and Technology (HKUST). Further Information can be found at the following URL: . Wai-Yeung Lam obtained his M.Phil. degree from the Hong Kong University of Science and Technology (HKUST) in 2003. His research thesis was based on the project “XCQ: A Framework for Querying Compressed XML Data.” He is currently working in industry. Peter Wood received his Ph.D. in Computer Science from the University of Toronto in 1989. He has previously studied at the University of Cape Town, South Africa, obtaining a B.Sc. degree in 1977 and an M.Sc. degree in Computer Science in 1982. Currently he is a senior lecturer at Birkbeck and a member of the Information Management and Web Technologies research group. His research interests include database and XML query languages, query optimisation, active and deductive rule languages, and graph algorithms. Mark Levene received his Ph.D. in Computer Science in 1990 from Birkbeck College, University of London, having previously been awarded a B.Sc. in Computer Science from Auckland University, New Zealand in 1982. He is currently professor of Computer Science at Birkbeck College, where he is a member of the Information Management and Web Technologies research group. His main research interests are Web search and navigation, Web data mining and stochastic models for the evolution of the Web. He has published extensively in the areas of database theory and web technologies, and has recently published a book called ‘An Introduction to Search Engines and Web Navigation’.