Stable methods for recognizing acronym-expansion pairs: from rule sets to hidden Markov models

A significant portion of currently available documents exist in the form of images, for instance, as scanned documents. Electronic documents produced by scanning and OCR software contain recognition errors. This paper uses an automatic approach to examine the selection and the effectiveness of searching techniques for possible erroneous terms for query expansion. The proposed method consists of two basic steps. In the first step, confused characters in erroneous words are located and editing operations are applied to create a collection of erroneous error-grams in the basic unit of the model. The second step uses query terms and error-grams to generate additional query terms, identify appropriate matching terms, and determine the degree of relevance of retrieved document images to the user's query, based on a vector space IR model. The proposed approach has been trained on 979 document images to construct about 2,822 error-grams and tested on 100 scanned Web pages, 200 advertisements and manuals, and 700 degraded images. The performance of our method is evaluated experimentally by determining retrieval effectiveness with respect to recall and precision. The results obtained show its effectiveness and indicate an improvement over standard methods such as vectorial systems without expanded query and 3-gram overlapping. Youssef Fataicha received his B.Sc. degree from Université de Rennes1, Rennes, France, in 1982. In 1984 he obtained his M.Sc. in computer science from Université de Rennes1, France. Between 1984 and 1986 he was a lecturer at the Université de Rennes1, France. He then served as engineer, from 1987 to 2000, at {Office de l'eau potable et de l'électricité} in Morocco. Since 2001 has been a Ph.D. student at the {école de Technologie Supérieure de l'Université du Québec} in Montreal, Québec, Canada. His research interests include pattern recognition, information retrieval, and image analysis. Mohamed Cheriet received his B.Eng. in computer science from {Université des Sciences et de Technologie d'Alger} (Bab Ezouar, Algiers) in 1984 and his M.Sc. and Ph.D., also in computer science, from the University of Pierre et Marie Curie (Paris VI) in 1985 and 1988, respectively. Dr. Cheriet was appointed assistant professor in 1992, associate professor in 1995, and full professor in 1998 in the Department of Automation Engineering, {école de Technologie Supérieure} of the University of Québec, Montreal. Currently he is the director of LIVIA, the Laboratory for Imagery, Vision and Artificial Intelligence at ETS, and an active member of CENPARMI, the Centre for Pattern Recognition and Machine Intelligence. Professor Cheriet's research focuses on mathematical modeling for signal and image processing (scale-space, PDEs, and variational methods), pattern recognition, character recognition, text processing, document analysis and recognition, and perception. He has published more than 100 technical papers in these fields. He was the co-chair of the 11th and the 13th Vision Interface Conferences held respectively in Vancouver in 1998 and in Montreal in 2000. He was also the general co-chair of the 8th International Workshop on Frontiers on Handwriting Recognition held in Niagara-on-the-Lake in 2002. He has served as associate editor of the International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI) since 2000. Dr. Cheriet is a senior member of IEEE. Jian Yun Nie is a professor in the computer science department (DIRO), Université de Montreal, Québec, Canada. His research focuses on problems related to information retrieval, including multilingual and multimedia information retrieval, as well as natural language processing. Ching Y. Suen received his M.Sc. (Eng.) from the University of Hong Kong and Ph.D. from the University of British Columbia, Canada. In 1972 he joined the Department of Computer Science of Concordia University, where he became professor in 1979 and served as chairman from 1980 to 1984 and as associate dean for research of the Faculty of Engineering and Computer Science from 1993 to 1997. He has guided/hosted 65 visiting scientists and professors and supervised 60 doctoral and master's graduates. Currently he holds the distinguished Concordia Research Chair in Artificial Intelligence and Pattern Recognition and is the Director of CENPARMI, the Centre for Pattern Recognition and Machine Intelligence.Professor Suen is the author/editor of 11 books and more than 400 papers on subjects ranging from computer vision and handwriting recognition to expert systems and computational linguistics. A Google search on “Ching Y. Suen” will show some of his publications. He is the founder of the International Journal of Computer Processing of Oriental Languages and served as its first editor-in-chief for 10 years. Presently he is an associate editor of several journals related to pattern recognition.A fellow of the IEEE, IAPR, and the Academy of Sciences of the Royal Society of Canada, he has served several professional societies as president, vice-president, or governor. He is also the founder and chair of several conference series including ICDAR, IWFHR, and VI. He has been the general chair of numerous international conferences, including the International Conference on Computer Processing of Chinese and Oriental Languages in August 1988 held in Toronto, International Conference on Document Analysis and Recognition held in Montreal in August 1995, and the International Conference on Pattern Recognition held in Québec City in August 2002.Dr. Suen has given 150 seminars at major computer companies and various government and academic institutions around the world. He has been the principal investigator of 25 industrial/government research contracts and is a grant holder and recipient of prestigious awards, including the ITAC/NSERC award from the Information Technology Association of Canada and the Natural Sciences and Engineering Research Council of Canada in 1992 and the Concordia “Research Fellow” award in 1998.     

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.     

Multi-Modal Locomotion Robotic Platform Using Leg-Track-Wheel Articulations

Other than from its sensing and processing capabilities, a mobile robotic platform can be limited in its use by its ability to move in the environment. Legs, tracks and wheels are all efficient means of ground locomotion that are most suitable in different situations. Legs allow to climb over obstacles and change the height of the robot, modifying its viewpoint of the world. Tracks are efficient on uneven terrains or on soft surfaces (snow, mud, etc.), while wheels are optimal on flat surfaces. Our objective is to work on a new concept capable of combining different locomotion mechanisms to increase the locomotion capabilities of the robotic platform. The design we came up with, called AZIMUT, is symmetrical and is made of four independent leg-track-wheel articulations. It can move with its articulations up, down or straight, allowing the robot to deal with three-dimensional environments. AZIMUT is also capable of moving sideways without changing its orientation, making it omnidirectional. By putting sensors on these articulations, the robot can also actively perceive its environment by changing the orientation of its articulations. Designing a robot with such capabilities requires addressing difficult design compromises, with measurable impacts seen only after integrating all of the components together. Modularity at the structural, hardware and embedded software levels, all considered concurrently in an iterative design process, reveals to be key in the design of sophisticated mobile robotic platforms.This research is supported financially by the Canada Research Chair (CRC) program, the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canadian Foundation for Innovation (CFI) and the Faculty of Engineering of the Université de Sherbrooke. Patent pending.François Michaud is the Canada Research Chairholder in Autonomous Mobile Robots and Intelligent Systems, and an Associate Professor at the Department of Electrical Engineering and Computer Engineering of the Université de Sherbrooke. He is the principal investigator of LABORIUS, a research laboratory working on applying AI methodologies in the design of intelligent autonomous systems that can assist humans in everyday lives. His research interests are architectural methodologies for intelligent decision making, autonomous mobile robotics, social robotics, robot learning and intelligent systems. He received his bachelors degree, Masters degree and Ph.D. degree in Electrical Engineering from the Université de Sherbrooke. He is a member of IEEE, AAAI and OIQ (Ordre des ingénieurs du Québec).Dominic Létourneau has a Bachelor degree in Computer Engineering and a Masters degree in Electrical Engineering from the Université de Sherbrooke. Since 2001, he is a research engineer at the LABORIUS Mobile Robotics and Intelligent Systems Laboratory. His research interests cover combination of systems and intelligent capabilities to increase the usability of autonomous mobile robots in the real world. His expertise lies in artificial vision, mobile robotics, robot programming and integrated design. He is a member of OIQ (Ordre des ingénieurs du Québec).Martin Arsenault has a Bachelor degree in Mechanical Engineering and from the Université de Sherbrooke. For AZIMUT, he developed the Direction subsystem.Yann Bergeron is a Mechanical Junior Engineer working in a consulting engineering firm, Groupe HBA. His field of activity is most oriented in industrial projects and construction. He received his bachelors degree in Mechanical Engineering from the University de Sherbrooke. For AZIMUT, he worked on the Track-Wheel subsystem. He is a member of OIQ (Ordre des ingénieurs du Québec) and JECQ (Jeunes entrepreneurs du Centre-du-Québec).Richard Cadrin has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. For AZIMUT, he worked on the Propulstion subsystem.Frédéric Gagnon has a Bachelor degree in Mechanical Engineering and from the Université de Sherbrooke. For AZIMUT, he designed the chassis and worked on the integration of the articulations, the bodywork and the hardware. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He also contributes in a mobile robotic.Marc-Antoine Legault has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke, and is currently pursuing a Masters degree at LABORIUS on serial-elastic actuators. He worked on AZIMUTs Propulsion subsystem. He also works on the design of other mobile robotic platforms. He is a member of OIQ (Ordre des ingénieurs du Québec).Mathieu Millette has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. For AZIMUT, he developed the Tensor subsystem and he designed and integrated the battery support inside the chassis. He is now working as a junior mechanical engineer in process and technical development in a third sector mill.Jean-François Paré graduated in Mechanical Engineering from the Université de Sherbrooke. He is also trained as a professional coach from R.I.C.K. (Réseau International de Coaching Kokopelli). He launched is own business in individual coaching, team coaching, team building and coaching workshops. For businesses and individuals, he assists people in reaching their well-being and efficiency and to manifest their leadership.Marie-Christine Tremblay has obtained a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. As a part of the AZIMUTõs team, she contributed the Track-Wheel subsystem and developed a new track with high adherence and wear resistance to climb stairs. She is working in the Engineering Department at Hydra-Fab Industriel, a company conceiving electro-hydraulic systems for high speed trains.Pierre Lepage has a Computer Engineering degree from the Université de Sherbrooke. For AZIMUT, he designed the user interface to control the robot and the propulsion system. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He is involved in research projects on coordinated behavior of a group of mobile robots. He is also actively involved in a mobile robotic startup.Yan Morin has an Electrical Engineering degree from the Université de Sherbrooke. For AZIMUT, he designed the electrical interface to control the motors of the robot. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He is also actively involved in a mobile robotic startup.Jonathan Bisson has a Bachelor degree in Computer Engineering and a Masters degree in Electrical Engineering from the Université de Sherbrooke. His contribution to AZIMUT was on the modular distributed computing architecture. His expertise lies in electronics, motor control, embedded systems and ultrasonic transducers.Serge Caron is technician in computer systems at the Department of Electrical Engineering and Computer Engineering of the Universit de Sherbrooke. His interests are in designing mobile robotic platforms, from four-legged to wheeled robots. He is also a writer for hobbyist robotic journals.     

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.     

Strong stable properties in distributed systems

Summary A stable property in a distributed system is a global property which once true, remains true forever. This paper refines this notion by formally introducing the concept ofstrong stable properties. A strong stable property has the nice property that it can be correctly evaluated on the consistent part of uncoordinated snapshots. Termination and deadlock are shown to be strong stable properties, whereas distributed garbage is not. We also show how to derive a simple generic algorithm for the detection of a strong stable property. The generic algorithm is illustrated by two examples: termination detection and deadlock detection. Incidentally the paper presents a very simple algorithm for termination detection. Andre Schiper has been a professor of Computer Science at EPFL (Federal Institute of Technology in Lausanne, Switzerland) since 1985, leading the Operating Systems laboratory. He graduated in Physics from the Federal Institute of technology in Zürich and received his Ph.D. in Computer Science from EPFL in 1980. In 1981–82 he spent one year at the University of Rennes, France. From 1983 to 1985, he was professor at the Engineering School in Yverdon, Switzerland. Between 1989 and 1991 André Schiper was head of the Department of Computer Science of EPFL, and during the academic year 1992–93 he was on sabbatical leave at Cornell University, Ithaca (NY). His research interests are in the areas of operating systems, distributed and fault-tolerant distributed systems, and parallelism. He is currently involved in the European Esprit project BROADCAST whose objective is the design and implementation of large scale distributed computing systems. Alain Sandoz graduated in Mathematics from the University of Neuchâtel, Switzerland, in 1984 and in Computer Science from the Federal Institute of Technology in Lausanne, Switzerland, in 1988. He received his Ph.D. in Computer Science from the Federal Institute of Technology in Lausanne in 1992. His dissertation was concerned with modelling causal relationships between transactions in distributed and replicated database systems. From 1992 to 1994 he was involved in research on fault-tolerant and large scale distributed computing systems. He is currently working on the development of information systems for the Swiss government.     

Frame-based representation of philosophical systems using a knowledge engineering tool

This article addresses the methodological problem of the non-linear representation of philosophical systems in a computerized knowledge base. It is a problem of knowledge representation as defined in the field of artificial intelligence. Instead of a purely theoretical discussion of the issue, we present selected results of a practical experiment which has in itself some theoretical significance. We show how one can represent different philosophies using CODE, a knowledge engineering system developed by artificial intelligence researchers. The hypothesis is that such a computer based representation of philosophical systems can give insight into their conceptual structure. We argue that computer aided text analysis can apply knowledge representation tools and techniques developed in artificial intelligence and we estimate how philosophers as well as knowledge engineers could gain from this cross-fertilization. This paper should be considered as an experiment report on the use of knowledge representation techniques in computer aided text analysis. It is part of a much broader project on the representation of conceptual structures in an expert system. However, we intentionally avoided technical issues related to either Computer Science or History of Philosophy to focus on the benefit to enhance traditional humanistic studies with tools and methods developed in AI on the one hand and the need to develop more appropriate tools on the other. Gilbert Boss is professor of Philosophy at Université Laval, Québec. He is the author of several books, including Les machines à penser. L'homme et l'ordinateur,Zurich: Grand Midi, 1987, and John Stuart Mill. Induction et utilité,Paris: PUF, 1990. His main fields of research are modern philosophy, philosophy of culture, philosophical discourse and systems, artificial intelligence. Maryvonne Longeart is professor of Computer Science at UQAH, Hull, Québec. Her research interests include object oriented design methodologies and knowledge representation. She received a PhD in Philosophy from the University of Ottawa in 1978 and a BSc in computer science in 1987. She contributed to the Encyclopédie philosophique universelle,PUF, 1992 and published several papers on the representation of complex conceptual systems.Douglas Skuce is professor of computer science at the University of Ottawa. He has worked in the area of knowledge engineering since his PhD (McGill, 1977). During 1978-present he has been developing the CODE system for various applications, including terminology and software development. Currently, his interests include designing ontologies for knowledge exchange and coupling large corpora to systems such as CODE.     

Hierarchies of parallel rewriting P systems — A survey

The paper is about some families of rewriting P systems, where the application of evolution rules is extended from the classical sequential rewriting to the parallel one (as, for instance, in Lindenmayer systems). As a result, consistency problems for the communication of strings may arise. Three variants of parallel rewriting P systems (already present in the literature) are considered here, together with the strategies they use to face the communication problem, and some parallelism methods for string rewriting are defined. We give a survey of all known results about each variant and we state some relations among the three variants, thus establishing hierarchies of parallel rewriting P systems. Various open problems related to the subject are also presented. Danicla Besozzi: She is assistant professor at the University of Milano. She received her M.S. in Mathematics (2000) from the University of Como and Ph.D. in Computer Science (2004) from the University of Milano. Her research interests cover topics in Formal Language Theory, Molecular Computing, Systems Biology. She is member of EATCS (European Association for Theoretical Computer Science) and EMCC (European Molecular Computing Consortium). Giancarlo Mauri: He is full professor of Computer Science at the University of Milano-Bicocca. His research interests are mainly in the area of theoretical computer science, and include: formal languages and automata, computational complexity, computational learning theory, soft computing techniques, cellular automata, bioinformatics and molecular computing. On these subjects, he published more than 150 scientific papers in international journals, contributed volumes and conference proceedings. Claudio Zandron: He received Ph.D. in Computer Science at the University of Milan, Italy, in 2001. Since 2002 he is assistant professor at the University of Milano-Bicocca, Italy. He is member of the EATCS (European Association for Theoretical Computer Science) and of EMCC (European Molecular Computing Consortium). His research interests are Molecular Computing (DNA and Membrane Computing) and Formal Languages.     

On some operations on strings suggested by gene assembly in ciliates

We define three operations on strings and languages suggested by the process of gene assembly in hypotrichous ciliates. This process is considered to be a prine example of DNA computing in vivo. This paper is devoted to some computational aspects of these operations from a formal language point of view. The closure of the classes of regular and context-free languages under these operations is settled. Then, we consider theld-macronuclear language of a given languageL, which consists of allld-macronuclear strings obtained from the strings ofL by iteratively applying the loop-direct repeat-excision. Finally, we discuss some open problems and further directions of research. Rudolf Freund: He received his master and doctor degree in computer science from the Vienna University of Technology, Austria, in 1980 and 1982, respectively. In 1986, he received his master degree in mathematics and physics from the University Vienna, Austria. In 1988 he joined the Vienna University of Technology in Austria, where he became an Associate Professor in September 1995. He has given various lectures in theoretical computer science, especially on formal languages and automata. His research interests include array and graph grammars, regulated rewritung, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields he is author of more than sixty scientific papers. Carlos Martín-Vide: He is Professor and Head of the Research Group on Mathematical Linguistics at Rovira i Virgili University, Tarragona, Spain. His specialities are formal language theory and mathematical linguistics. His last volume edited is Where Mathematics, Computer Science, Linguistics and Biology Meet (Kluwer, 2001, with V. Mitrana). He published 150 papers in conference proceedings and journals such as: Acta Informatica, BioSystems. Computational Linguistics, Computers and Artificial Intelligence, Information Processing Letters, Information Sciences, International Journal of Computer Mathematics, New Generation Computing, Publicationes Mathematicae Debrecen, and Theoretical Computer Science. He is the editor-in-chief of the journal Grammars (Kluwer), and the chairman of the 1st International PhD School in Formal Languages and Applications (2001–2003). Victor Mitrana, Ph.D.: He is Professor of Computer Science at the Faculty of Mathematics, University of Bucharest. He received his MSc and PhD from the University of Bucharest in 1986 and 1993, respectively. In 1999 he was awarded with the “Gheorghe Lazar” Prize for Mathematics of the Romanian Academy. His research interests include: formal language theory and applications, combinatorics on words, computational models inspired from biology, mathematical linguistics. In these areas, he published three books, more than 100 papers, and edited two books. He is an associate editor of “The Korean Journal of Computational and Applied Mathematics” and an editor of “Journal of Universal Computer Science”.     

A Framework for the Generation of Adaptive Courses Based on Semantic Metadata

This approach proposes the creation and management of adaptive learning systems by combining component technology, semantic metadata, and adaptation rules. A component model allows interaction among components that share consistent assumptions about what each provides and each requires of the other. It allows indexing, using, reusing, and coupling of components in different contexts powering adaptation. Our claim is that semantic metadata are required to allow a real reusing and assembling of educational component. Finally, a rule language is used to define strategies to rewrite user query and user model. The former allows searching components developing concepts not appearing in the user query but related with user goals, whereas the last allow inferring user knowledge that is not explicit in user model.John Freddy Duitama received his M.Sc. degree in system engineering from the University of Antioquia -Colombia (South America). He is currently a doctoral candidate in the GET – Institut National des Télécommunications, Evry France. This work is sponsored by the University of Antioquia, where he is assistant professor.His research interest includes semantic web and web-based learning systems, educational metadata and learning objects.Bruno Defude received his Ph.D. in Computer Science from the University of Grenoble (I.N.P.G) in 1986. He is currently Professor in the Department of Computer Science at the GET - Institut National des Télécommunications, Evry France where he leads the SIMBAD project (Semantic Interoperability for MoBile and ADaptive applications).His major field of research interest is databases and semantic web, specifically personalized data access, adaptive systems, metadata, interoperability and semantic Peer-to-peer systems with elearning as a privileged application area.He is a member of ACM SIGMOD.Amel Bouzeghoub received a degree of Ph.D. in Computer Sciences at Pierre et Marie Curie University, France.In 2000, she joined the Computer Sciences Department of GET-INT (Institut National des Telecommunications) at Evry (France) as an associate professor.Her research interests include topics related to Web-based Learning Systems, Semantic Metadata for learning resources, Adaptive Learning Systems and Intelligent Tutoring Systems.Claire Lecocq received an Engineer Degree and a Ph.D. in Computer Sciences respectively in 1994 and 1999. In 1997, she joined the Computer Sciences Department at GET-INT (Institut National des Télécommunications) of Evry, France, as an associate professor. Her first research interests included spatial databases and visual query languages. She is now working on adaptive learning systems, particularly on semantic metadata and user models.     

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.     

Life sciences grid in EUROGRID and GRIP projects

In this paper we describe deployment of most important life sciences applications on the grid. The build grid is heterogenous and consist of systems of different architecture as well as operating systems and various middleware. We have used UNICORE infrastructure as framework for development dedicated user interface to the number of existing computational chemistry codes and molecular biology databases. Developed solution allows for access to the resources provided with UNICORE as well as Globus with exactly the same interface which gives access to the general grid functionality such as single login, job submission and control mechanism. Jarosław Wypychowski: He is a student at the Faculty of Mathematics and Computer Science, Warsaw University, Poland. He is involved in the development of grid tools. He has been working as programmer in the private company. Jarosław Pytliński, M.Sc.: He received his M.Sc. in 2002 from Department of Mathematic and Computer Science of Nicolaus Copernicus University in Torun. His thesis on “Quantum Chemistry Computations in Grid Environment” was distincted in XIX Polish Contest for the best M.Sc. Thesis of Computer Science. He also worked in Laboratory of High Performance Systems at UCI, Torun. His interests are Artificial Intelligence and GRID technology. Łukasz Skorwider, M.Sc.: He is programmer in the private pharmaceutical company. He obtained M.Sc. degree from the Faculty of Mathematics and Computer Science N. Copernicus University. As graduate student he was involved in the development of grid tools for drug design. His private and professional interest is Internet technology. Mirosław Nazaruk, M.Sc.: He is a senior computer and network administrator at ICM Warsaw University. He provides professional support for the users of the high performance facilities located at the ICM. He obtained M.Sc. in Computer Science from Warsaw University in 1991. Before joining ICM, he was a member of technical staff at Institute of Applied Mathematics, Warsaw University. Krzysztof Benedyczak: He is a student at the Faculty of Mathematics and Computer Science, N. Copernicus University, Torun, Poland. He is involved in the development of grid tools. Michał Wroński: He is a student at the Faculty of Mathematics and Computer Science, N. Copernicus University, Torun, Poland. He is involved in the development of grid tools. Piotr Bała, Ph.D.: He is an adiunkt at Faculty of Mathematics and Computer Science N. Copernicus University, Torun, Poland, and tightly cooperates with ICM, Warsaw University. He obtained Ph.D. in Physics in 1993 in Institute of Physics, N. Copernicus University and in 2000 habilitation in physics. From 2001 he was appointed director of Laboratory of Parallel and Distributed Processing at Faculty of Mathematics, N. Copernicus University. His main research interest is development and application of Quantum-Classical Molecular Dynamics and Approximated Valence Bond method to study of enzymatic reactions in biological systems. In the last few years, he has been involved in development of parallel and grid tools for large scale scientific applications.     

Automated support for deriving test requirements from UML statecharts

Many statechart-based testing strategies result in specifying a set of paths to be executed through a (flattened) statechart. These techniques can usually be easily automated so that the tester does not have to go through the tedious procedure of deriving paths manually to comply with a coverage criterion. The next step is then to take each test path individually and derive test requirements leading to fully specified test cases. This requires that we determine the system state required for each event/transition that is part of the path to be tested and the input parameter values for all events and actions associated with the transitions. We propose here a methodology towards the automation of this procedure, which is based on a careful normalization and analysis of operation contracts and transition guards written with the Object Constraint Language (OCL). It is illustrated by one case study that exemplifies the steps of our methodology and provides a first evaluation of its applicability. The scope of the testing activity depends on what is modeled by the statechart. If the statechart models the behavior of a single class, then it can be used to support unit testing. If the behavior of a class-cluster, a subsystem or a component is modeled, then we are concerned with integration testing. If the whole system is modeled, then the focus of statechart-based testing is system testing. Lionel C. Briand is on the faculty of the Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada, where he founded and leads the Software Quality Engineering Laboratory (http://www.sce.carleton.ca/Squall/ Squall.htm). He has been granted the Canada Research Chair in Software Quality Engineering and is also a visiting professor at the Simula laboratories, University of Oslo, Norway. Before that he was the software quality engineering department head at the Fraunhofer Institute for Experimental Software Engineering, Germany. Dr. Lionel also worked as a research scientist for the Software Engineering Laboratory, a consortium of the NASA Goddard Space Flight Center, CSC, and the University of Maryland. He has been on the program, steering, or organization committees of many international, IEEE conferences such as ICSE, ICSM, ISSRE, and METRICS. He is the coeditor-in-chief of Empirical Software Engineering (Springer) and is a member of the editorial board of Systems and Software Modeling (Springer). He was on the board of IEEE Transactions on Software Engineering from 2000 to 2004. His research interests include: object-oriented analysis and design, inspections and testing in the context of object-oriented development, quality assurance and control, project planning and risk analysis, and technology evaluation. Lionel received the BSc and MSc degrees in geophysics and computer systems engineering from the University of Paris VI, France. He received the PhD degree in computer science, with high honors, from the University of Paris XI, France. Yvan Labiche received the BSc in Computer System Engineering, from the graduate school of engineering: CUST (Centre Universitaire des Science et Techniques, Clermont-Ferrand), France. He completed a Master of fundamental computer science and production systems in 1995 (Université Blaise Pascal, Clermont Ferrand, France). While doing his Ph.D. in Software Engineering, completed in 2000 at LAAS/CNRS in Toulouse, France, Yvan worked with Aerospatiale Matra Airbus (now EADS Airbus) on the definition of testing strategies for safety-critical, on-board software, developed using object-oriented technologies. In January 2001, Dr. Yvan Labiche joined the Department of Systems and Computer Engineering at Carleton University, as an Assistant Professor. His research interests include: object-oriented analysis and design, software testing in the context of object-oriented development, and technology evaluation. He is a member of the IEEE. Jim (Jingfeng) Cui completed his BSc in Industrial Automation Control, from the School of Information and Engineering, Northeastern University, China. He received a Master of Applied Science (specialization in Software Engineering) in 2004 from the Ottawa-Carleton Institute of Electrical and Computer Engineering, Ottawa, Canada. While in his graduate study, he was awarded the Ontario Graduate Scholarship of Science and Technology. He is now a senior Software Architect in Sunyard System & Engineering Co.Ltd., China. His interest includes Object-Oriented Software Development, Quality Assurance, and Content Management System.     

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.     

DocXS distributed operator construction and execution system

In the field of computer vision and pattern recognition, data processing and data analysis tasks are often implemented as a consecutive or parallel application of more-or-less complex operations. In the following we will present DocXS, a computing environment for the design and the distributed and parallel execution of such tasks. Algorithms can be programmed using an Eclipse-based user interface, and the resulting Matlab and Java operators can be visually connected to graphs representing complex data processing workflows. DocXS is platform independent due to its implementation in Java, is freely available for noncommercial research, and can be installed on standard office computers. One advantage of DocXS is that it automatically takes care about the task execution and does not require its users to care about code distribution or parallelization. Experiments with DocXS show that it scales very well with only a small overhead. The text was submitted by the authors in English. Steffen Wachenfeld received B.Sc. and M.Sc. (honors) degrees in Information Systems in 2003 and 2005 from the University of Muenster, Germany, and an M.Sc. (honors) degree in Computer Science in 2003 from the University of Muenster. He is currently a research fellow and PhD student in the Computer Science at the Dept. of Computer Science, University of Muenster. His research interests include low resolution text recognition, computer vision on mobile devices, and systems/system architectures for computer vision and image analysis. He is author or coauthor of more than ten scientific papers and a member of IAPR. Tobias Lohe, M.Sc. degree in Computer Science in 2007 from the University of Muenster, Germany, is currently a research associate and PhD student in Computer Science at the Institute for Robotics and Cognitive Systems, University of Luebeck, Germany. His research interests include medical imaging, signal processing, and robotics for minimally invasive surgery. Michael Fieseler is currently a student of Computer Science at the University of Muenster, Germany. He has participated in research in the field of computer vision and medical imaging. Currently he is working on his Master thesis on depth-based image rendering (DBIR). Xiaoyi Jiang studied Computer Science at Peking University, China, and received his PhD and Venia Docendi (Habilitation) degree in Computer Science from the University of Bern, Switzerland. In 2002 he became an associate professor at the Technical University of Berlin, Germany. Since October 2002 he has been a full professor at the University of Münster, Germany. He has coauthored and coedited two books published by Springer and has served as the co-guest-editor of two special issues in international journals. Currently, he is the Coeditor-in-Chief of the International Journal of Pattern Recognition and Artificial Intelligence. In addition he also serves on the editorial advisory board of the International Journal of Neural Systems and the editorial board of IEEE Transactions on Systems, Man, and Cybernetics—Part B, the International Journal of Image and Graphics, Electronic Letters on Computer Vision and Image Analysis, and Pattern Recognition. His research interests include medical image analysis, vision-based man-machine interface, 3D image analysis, structural pattern recognition, and mobile multimedia. He is a member of IEEE and a Fellow of IAPR.     

A logic-based integration of active and deductive databases

A logic-based approach to the specification of active database functionality is presented which not only endows active databases with a well-defined and well-understood formal semantics, but also tightly integrates them with deductive databases. The problem of endowing deductive databases with rule-based active behaviour has been addressed in different ways. Typical approaches include accounting for active behaviour by extending the operational semantics of deductive databases, or, conversely, accounting for deductive capabilities by constraining the operational semantics of active databases. The main contribution of the paper is an alternative approach in which a class of active databases is defined whose operational semantics is naturally integrated with the operational semantics of deductive databases without either of them strictly subsuming the other. The approach is demonstrated via the formalization of the syntax and semantics of an active-rule language that can be smoothly incorporated into existing deductive databases, due to the fact that the standard formalization of deductive databases is reused, rather than altered or extended. One distinctive feature of the paper is its use of ahistory, as defined in the Kowalski-Sergot event-calculus, to define event occurrences, database states and actions on these. This has proved to be a suitable foundation for a comprehensive logical account of the concept set underpinning active databases. The paper thus contributes a logical perspective to the ongoing task of developing a formal theory of active databases. Alvaro Adolfo Antunes Fernandes, Ph.D.: He received a B.Sc. in Economics (Rio de Janeiro, 1984), an M.Sc. in Knowledge-Based Systems (Edinburgh, 1990) and a Ph.D. in Computer Science (Heriot-Watt, 1995). He worked as a Research Associate at Heriot-Watt University from December 1990 until December 1995. In January 1996 he joined the Department of Mathematical and Computing Sciences at Goldsmiths College, University of London, as a Lecturer. His current research interests include advanced data- and knowledge-base technology, logic programming, and software engineering. M. Howard Williams, Ph.D., D.Sc.: He obtained his Ph.D. in ionospheric physics and recently a D.Sc. in Computer Science. He was appointed as the first lecturer in Computer Science at Rhodes University in 1970. During the following decade he rose to Professor of Computer Science and in 1980 was appointed as Professor of Computer Science at Heriot-Watt University. From 1980 to 1988 he served as Head of Department and then as director of research until 1992. He is now head of the Database Research Group at Heriot-Watt University. His current research interests include active databases, deductive objectoriented databases, spatial databases, parallel databases and telemedicine. Norman W. Paton, Ph.D.: He received a B.Sc. in Computing Science from the University of Aberdeen in 1986. From 1986 to 1989 he worked as a Research Assistant at the University of Aberdeen, receiving a Ph. D. in 1989. From 1989 to 1995 he was a Lecturer in Computer Science at Heriot-Watt University. Since July 1995, he has been a Senior Lecturer in Department of Computer Science at the University of Manchester. His current research interests include active databases, deductive object-oriented databases, spatial databases and database interfaces.     

Blackboard relations in the μLog coordination model

This paper describescoordination relations, that are relations that induce the presence or absence of data on some dataspaces from the presence or absence of other data on other dataspaces. To that end we build upon previous work on the μLog model and show that the coordination relations can be easily incorporated in it. This is achieved, on the one hand, by means of novel auxiliary operations, not classically used in Linda-like languages, and, on the other hand, by a translation technique reducing the extended μLog model to the core model augmented with the auxiliary operations. Among the most significant ones are multiple read and get operations on a blackboard, readall and getall operations, and tests for the absence of data on blackboards. Although simple, the form of coordination relations we propose is quite powerful as evidenced by a few examples including relations coming from the object-oriented paradigm such as inheritance relations. Jean-Marie Jacquet, Ph.D.: He is Professor at the Institute of Informatics at the University of Namur, Belgium, and, at an honorary title, Research Associate of the Belgian National Fund for Scientific Research. He obtained a Master in Mathematics from the University of Liège in 1982, a Master in Computer Science from the University of Namur in 1984 and a Ph.D. in Computer Science from the University of Namur in 1989. His research interest are in Programming Languages and Coordination models. He has served as a reviewer and program committee member of several conferences. Koen de Bosschere, Ph.D.: He holds the degree of master of Science in Engineering of the Ghent University, and a Ph.D. from the same University. He is currently research associate with the Fund for Scientific Research — Flanders and senior lecturer at the Ghent University, where he teaches courses on computer architecture, operating systems and declarative programming languages. His research interests are coordination in parallel logic programming, computer architecture and systems software.     

Applying language modeling to session identification from database trace logs

A database session is a sequence of requests presented to the database system by a user or an application to achieve a certain task. Session identification is an important step in discovering useful patterns from database trace logs. The discovered patterns can be used to improve the performance of database systems by prefetching predicted queries, rewriting the current query or conducting effective cache replacement.In this paper, we present an application of a new session identification method based on statistical language modeling to database trace logs. Several problems of the language modeling based method are revealed in the application, which include how to select values for the parameters of the language model, how to evaluate the accuracy of the session identification result and how to learn a language model without well-labeled training data. All of these issues are important in the successful application of the language modeling based method for session identification. We propose solutions to these open issues. In particular, new methods for determining an entropy threshold and the order of the language model are proposed. New performance measures are presented to better evaluate the accuracy of the identified sessions. Furthermore, three types of learning methods, namely, learning from labeled data, learning from semi-labeled data and learning from unlabeled data, are introduced to learn language models from different types of training data. Finally, we report experimental results that show the effectiveness of the language model based method for identifying sessions from the trace logs of an OLTP database application and the TPC-C Benchmark. Xiangji Huang joined York University as an Assistant Professor in July 2003 and then became a tenured Associate Professor in May 2006. Previously, he was a Post Doctoral Fellow at the School of Computer Science, University of Waterloo, Canada. He did his Ph.D. in Information Science at City University in London, England, with Professor Stephen E. Robertson. Before he went into his Ph.D. program, he worked as a lecturer for 4 years at Wuhan University. He also worked in the financial industry in Canada doing E-business, where he was awarded a CIO Achievement Award, for three and half years. He has published more than 50 refereed papers in journals, book chapter and conference proceedings. His Master (M.Eng.) and Bachelor (B.Eng.) degrees were in Computer Organization & Architecture and Computer Engineering, respectively. His research interests include information retrieval, data mining, natural language processing, bioinformatics and computational linguistics. Qingsong Yao is a Ph.D. student in the Department of Computer Science and Engineering at York University, Toronto, Canada. His research interests include database management systems and query optimization, data mining, information retrieval, natural language processing and computational linguistics. He earned his Master's degree in Computer Science from Institute of Software, Chinese Academy of Science in 1999 and Bachelor's degree in Computer Science from Tsinghua University. Aijun An is an associate professor in the Department of Computer Science and Engineering at York University, Toronto, Canada. She received her Bachelor's and Master's degrees in Computer Science from Xidian University in China. She received her PhD degree in Computer Science from the University of Regina in Canada in 1997. She worked at the University of Waterloo as a postdoctoral fellow from 1997 to 1999 and as a research assistant professor from 1999 to 2001. She joined York University in 2001. She has published more than 60 papers in refereed journals and conference proceedings. Her research interests include data mining, machine learning, and information retrieval.     

Capabilities of outlier detection schemes in large datasets,framework and methodologies

Outlier detection is concerned with discovering exceptional behaviors of objects. Its theoretical principle and practical implementation lay a foundation for some important applications such as credit card fraud detection, discovering criminal behaviors in e-commerce, discovering computer intrusion, etc. In this paper, we first present a unified model for several existing outlier detection schemes, and propose a compatibility theory, which establishes a framework for describing the capabilities for various outlier formulation schemes in terms of matching users'intuitions. Under this framework, we show that the density-based scheme is more powerful than the distance-based scheme when a dataset contains patterns with diverse characteristics. The density-based scheme, however, is less effective when the patterns are of comparable densities with the outliers. We then introduce a connectivity-based scheme that improves the effectiveness of the density-based scheme when a pattern itself is of similar density as an outlier. We compare density-based and connectivity-based schemes in terms of their strengths and weaknesses, and demonstrate applications with different features where each of them is more effective than the other. Finally, connectivity-based and density-based schemes are comparatively evaluated on both real-life and synthetic datasets in terms of recall, precision, rank power and implementation-free metrics. Jian Tang received an MS degree from the University of Iowa in 1983, and PhD from the Pennsylvania State University in 1988, both from the Department of Computer Science. He joined the Department of Computer Science, Memorial University of Newfoundland, Canada, in 1988, where he is currently a professor. He has visited a number of research institutions to conduct researches ranging over a variety of topics relating to theories and practices for database management and systems. His current research interests include data mining, e-commerce, XML and bioinformatics. Zhixiang Chen is an associate professor in the Computer Science Department, University of Texas-Pan American. He received his PhD in computer science from Boston University in January 1996, BS and MS degrees in software engineering from Huazhong University of Science and Technology. He also studied at the University of Illinois at Chicago. He taught at Southwest State University from Fall 1995 to September 1997, and Huazhong University of Science and Technology from 1982 to 1990. His research interests include computational learning theory, algorithms and complexity, intelligent Web search, informational retrieval, and data mining. Ada Waichee Fu received her BSc degree in computer science in the Chinese University of Hong Kong in 1983, and both MSc and PhD degrees in computer science in Simon Fraser University of Canada in 1986, 1990, respectively; worked at Bell Northern Research in Ottawa, Canada, from 1989 to 1993 on a wide-area distributed database project; joined the Chinese University of Hong Kong in 1993. Her research interests are XML data, time series databases, data mining, content-based retrieval in multimedia databases, parallel, and distributed systems. David Wai-lok Cheung received the MSc and PhD degrees in computer science from Simon Fraser University, Canada, in 1985 and 1989, respectively. He also received the BSc degree in mathematics from the Chinese University of Hong Kong. From 1989 to 1993, he was a member of Scientific Staff at Bell Northern Research, Canada. Since 1994, he has been a faculty member of the Department of Computer Science in the University of Hong Kong. He is also the Director of the Center for E-Commerce Infrastructure Development. His research interests include data mining, data warehouse, XML technology for e-commerce and bioinformatics. Dr. Cheung was the Program Committee Chairman of the Fifth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2001), Program Co-Chair of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2005). Dr. Cheung is a member of the ACM and the IEEE Computer Society.     

A Metadata Service for Integrated Management of Knowledges Related to Coastal Areas

The research outlined in this paper is part of a wider research program named SYSCOLAG (Coastal and LAGoonal SYStems in Languedoc-Roussillon area, France) dedicated to sustainable coastal management. The main objective of this program is to build up a communication infrastructure to improve the exchange of information and knowledge between the various scientific disciplines involved in the research. In order to ensure the sharing of resources without affecting the autonomy and independance of the partners, we propose a three-level infrastructure (resources, federation and knowledge access) based on a metadata service (using ISO 19115 standard for geographic information metadata) completed by a common vocabulary (ontology).The Syscolag research program (COastal and LAGoonal SYStems) is funded by Languedoc Roussillon authority.Julien Barde is currently a Ph.D. student in Computer Science at the LIRMM (the Computer Science, Robotic and Microelectronic Laboratory of the University of Montpellier II, France) under the guidance of Thérèse Libourel and Pierre Maurel since 2002. He works for a research program of Integrated Coastal Management to improve knowledge sharing between the stakeholders of Languedoc Roussillon coastal area. He has received his engineer/M.Sc. degrees in Oceanology Sciences and Spatial Information Treatment from the National Superior Agronomic School of Rennes (ENSAR, Brittany, France) in 2000 and 2001. He has experience in Computer Science, Remote sensing, GIS and oceanology.Thérèse Libourel is a Senior Lecturer in Computer Science from the Conservatoire National des Arts et Métiers (CNAM), currently at the LIRMM (the Computer Science, Robotic and Microelectronic Laboratory of the University of Montpellier II, France) since 1994. She holds a Ph.D. and a habilitation thesis in Computer Science from the University of Montpellier II (France). Among others, her research interests are oriented towards object oriented design, reuse of software components, object oriented databases and evolution, and data models for spatial and temporal information systems.Pierre Maurel is a research engineer in Cemagref (France). He received his Diploma on Agronomy Engineering from ESAP high school (France) in 1986 and his M.Sc. on quantitative geography in 1990 from Avignon University (France). In the past, he performed research and teaching in satellite image processing and GIS for environmental and water applications. His current scientific interests include the development of methods for the design of multi-partners geographic information systems, the use of metadata within Spatial Data Infrastructures and the integration of Geographic Information technologies to support public participation in the field of Integrated River Basin Management (HarmoniCOP European project).