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.     

PAN: A portable,parallel Prolog: Its design,realisation and performance

PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for automatically extracting and exploiting AND and OR parallelism in ordinary Prolog programs. PAN incorporates a range of compile-time and run-time techniques to deliver the performance benefits of parallel execution while rertaining sequential execution semantics. Several examples illustrate the efficiency of the controls that facilitate the execution of logic programs in a distributed manner and identify the class of applications that benefit from distributed platforms like PAN. George Xirogiannis, Ph.D.: He received his B.S. in Mathematics from the University of Ioannina, Greece in 1993, his M.S in Artificial Intelligence from the University of Bristol in 1994 and his Ph.D. in Computer Science from Heriot-Watt University, Edinburgh in 1998. His Ph.D. thesis concerns the automated execution of Prolog on distributed heterogeneous multi-processors. His research interests have progressed from knowledge-based systems to distributed logic programming and data mining. Currently, he is working as a senior IT consultant at Pricewaterhouse Coopers. He is also a Research Associate at the National Technical University of Athens, researching in knowledge and data mining. Hamish Taylor, Ph.D.: He is a lecturer in Computer Science in the Computing and Electrical Engineering Department of Heriot-Watt University in Edinburgh. He received M.A. and MLitt degrees in philosophy from Cambridge University and an M.S. and a Ph.D. degree in computer science from Heriot-Watt University, Scotland. Since 1985 he has worked on research projects concerned with implementing concurrent logic programming languages, developing formal models for automated reasoning, performance modelling parallel relational database systems, and visualisizing resources in shared web caches. His current research interests are in applications of collaborative virtual environments, parallel logic programming and networked computing technologies.     

Temporal disjunctive logic programming

In this paper we introduce the logic programming languageDisjunctive Chronolog which combines the programming paradigms of temporal and disjunctive logic programming. Disjunctive Chronolog is capable of expressing dynamic behaviour as well as uncertainty, two notions that are very common in a variety of real systems. We present the minimal temporal model semantics and the fixpoint semantics for the new programming language and demonstrate their equivalence. We also show how proof procedures developed for disjunctive logic programs can be easily extended to apply to Disjunctive Chronolog programs. Manolis Gergatsoulis, Ph.D.: He received his B.Sc. in Physics in 1983, the M.Sc. and the Ph.D. degrees in Computer Science in 1986 and 1995 respectively all from the University of Athens, Greece. Since 1996 he is a Research Associate in the Institute of Informatics and Telecommunications, NCSR ‘Demokritos’, Athens. His research interests include logic and temporal programming, program transformations and synthesis, as well as theory of programming languages. Panagiotis Rondogiannis, Ph.D.: He received his B.Sc. from the Department of Computer Engineering and Informatics, University of Patras, Greece, in 1989, and his M.Sc. and Ph.D. from the Department of Computer Science, University of Victoria, Canada, in 1991 and 1994 respectively. From 1995 to 1996 he served in the Greek army. From 1996 to 1997 he was a visiting professor in the Department of Computer Science, University of Ioannina, Greece, and since 1997 he is a Lecturer in the same Department. In January 2000 he was elected Assistant Professor in the Department of Informatics at the University of Athens. His research interests include functional, logic and temporal programming, as well as theory of programming languages. Themis Panayiotopoulos, Ph.D.: He received his Diploma on Electrical Engineering from the Department of Electrical Engineering, National Technical Univesity of Athens, in 1984, and his Ph.D. on Artificial Intelligence from the above mentioned department in 1989. From 1991 to 1994 he was a visiting professor at the Department of Mathematics, University of the Aegean, Samos, Greece and a Research Associate at the Institute of Informatics and Telecommunications of “Democritos” National Research Center. Since 1995 he is an Assistant Prof. at the Department of Computer Science, University of Piraeus. His research interests include temporal programming, logic programming, expert systems and intelligent agent architectures.     

Transformational methodology for proving termination of logic programs

A methodology for proving the termination of well-moded logic programs is developed by reducing the termination problem of logic programs to that of term rewriting systems. A transformation procedure is presented to derive a term rewriting system from a given well-moded logic program such that the termination of the derived rewrite system implies the termination of the logic program for all well-moded queries under a class of selection rules. This facilitates applicability of a vast source of termination orderings proposed in the literature on term rewriting, for proving termination of logic programs. The termination of various benchmark programs has been established with this approach. Unlike other mechanizable approaches, the proposed approach does not require any preprocessing and works well, even in the presence of mutual recursion. The transformation has also been implemented as a front end to Rewrite Rule Laboratory (RRL) and has been used in establishing termination of nontrivial Prolog programs such as a prototype compiler for ProCoS, PL₀ language.     

P — A logic — a compositional proof system for distributed programs

Summary This paper describes a compositional proof system called P-A logic for establishing weak total correctness and weak divergence correctness of CSP-like distributed programs with synchronous and asynchronous communication. Each process in a network is specified using logical assertions in terms of a presuppositionPre and an affirmationAff as a triple {Pre}S{Aff}. For purely sequential programs, these triples reduce to the familiar Hoare triples. In distributed programs, P-A triples allow the behaviour of a process to be specified in the context of assumptions about its communications with the other processes in the network. Safety properties of process communications, and progress properties such as finiteness and freedom from divergence can be proved. An extension of P-A logic allowing proof of deadlock freedom is outlined. Finally, proof rules for deriving some liveness properties of a program from its P-A logic specification are discussed; these properties have the form Q untilR, whereQ, R are assertions over communication traces. Other liveness properties may be derived from these properties using the rules of temporal logic. Paritosh Kulin Pandya received his Master's degree in Computer Science from the Indian Institute of Technology, Kanpur in 1982, and a Ph.D. from the Tata Institute of Fundamental Research in 1988 where he is currently employed. He has worked as a Research Officer in the Programming Research Group of the Oxford University from 1988 to 1991. Mathai Joseph has since 1985 been professor of Computer Science at the University of Warwick where he leads a group working on developing formal techniques for specifying and implementing realtime and fault-tolerant systems.Supported in part by Visiting Fellowships awarded by the Science and Engineering Research Council (research grant GR/D 90918) and the British Council     

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.     

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.     

A program specialiser for meta-level compositions of logic programs

Metal-level compositions of object logic programs are naturally implemented by means of meta-programming techniques. Metainterpreters defining program compositions however suffer from a computational overhead that is due partly to the interpretation layer present in all meta-programs, and partly to the specific interpretation layer needed to deal with program compositions. We show that meta-interpreters implementing compositions of object programs can be fruitfully specialised w.r.t. meta-level queries of the form Demo (E, G), where E denotes a program expression and G denotes a (partially instantiated) object level query. More precisely, we describe the design and implementation of declarative program specialiser that suitably transforms such meta-interpreters so as to sensibly reduce — if not to completely remove — the overhead due to the handling of program compositions. In many cases the specialiser succeeds in eliminating also the overhead due to meta-interpretation. Antonio Brogi, Ph.D.: He is currently assistant professor in the Department of Computer Science at the University of Pisa, Italy. He received his Laurea Degree in Computer Science (1987) and his Ph. D. in Computer Science (1993) from the University of Pisa. His research interests include programming language design and semantics, logic programming, deductive databases, and software coordination. Simone Contiero: He is currently a Ph. D. student at the Department of Computer Science, University of Pisa (Italy). He received his Laurea Degree in Computer Science from the University of Pisa in 1994. His research interests are in high-level programming languages, metaprogramming and logic-based coordination of software.     

A General Probability Formula of the Number of Location Areas＇ Boundaries Crossed by a Mobile Between Two Successive Call Arrivals

Mobility management is a challenging topic in mobile computing environment. Studying the situation of mobiles crossing the boundaries of location areas is significant for evaluating the costs and performances of various location management strategies. Hitherto, several formulae were derived to describe the probability of the number of location areas‘ boundaries crossed by a mobile. Some of them were widely used in analyzing the costs and performances of mobility management strategies. Utilizing the density evolution method of vector Markov processes, we propose a general probability formula of the number of location areas‘ boundaries crossed by a mobile between two successive calls. Fortunately, several widely-used formulae are special cases of the proposed formula.     

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.     

A Fuzzy set based approach to generalized landscape theory of aggregation

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

Preference queries in deductive databases

Traditional database query languages such as datalog and SQL allow the user to specify only mandatory requirements on the data to be retrieved from a database. In many applications, it may be natural to express not only mandatory requirements but also preferences on the data to be retrieved. Lacroix and Lavency¹⁰⁾ extended SQL with a notion of preference and showed how the resulting query language could still be translated into the domain relational calculus. We explore the use of preference in databases in the setting of datalog. We introduce the formalism of preference datalog programs (PDPs) as preference logic programs without uninterpreted function symbols for this purpose. PDPs extend datalog not only with constructs to specify which predicate is to be optimized and the criterion for optimization but also with constructs to specify which predicate to be relaxed and the criterion to be used for relaxation. We can show that all of the soft requirements in Reference¹⁰) can be directly encoded in PDP. We first develop anaively-pruned bottom-up evaluation procedure that is sound and complete for computing answers to normal and relaxation queries when the PDPs are stratified, we then show how the evaluation scheme can be extended to the case when the programs are not necessarily stratified, and finally we develop an extension of themagic templates method for datalog¹⁴) that constructs an equivalent but more efficient program for bottom-up evaluation. Kannan Govindarajan, Ph.D.: He obtained his bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Madras, and he completed his Ph.D. degree in Computer Science from the State University of New York at Buffalo. His dissertation research was on optimization and relaxation techniques for logic languages. His interests lie in the areas of programming languages, databases, and distributed systems. He currently leads the trading community effort in the E-speak Operation in Hewlett Packard Company. Prior to that, he was a member of the Java Products Group in Oracle Corporation. Bharat Jayaraman, Ph.D.: He is a 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 (1975), and his Ph.D. from the University of Utah (1981). His research interests are in programming languages and declarative modeling of complex systems. Dr. Jayaraman has published over 50 papers in refereed conferences and journals. 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. Surya Mantha, Ph.D.: He is a manager in the Communications and Software Services Group of Pittiglio Rabin Todd & McGrath (PRTM), a management consulting firm serving high technology industries. He obtained a bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Kanpur, an MBA in Finance and Competitive Strategy from the University of Rochester, and a Ph.D. in Computer Science from the University of Utah (1991). His research interests are in the modeling of complex business processes, inter-enterprise application integration, and business strategy. Dr. Mantha has two US patents, and has published over 10 research papers. Prior to joining PRTM, he was a researcher and manager in the Architecture and Document Services Technology Center at Xerox Corporation in Rochester, New York.     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

Anti-aliased rendering of water surface

Water surface is one of the most important components of landscape scenes. When rendering spacious water surface such as that of the lakes and reservoirs, aliasing and/or moiré artifacts frequently occur in the regious far from the viewpoint. This is because water surface consists of stochastic water waves which are usually modeled by periodic bump mapping. The incident rays on the water surface are actually scattered by the bumped waves, and the reflected rays at each sample point are distributed in a solid angle. To get rid of the artifacts of moiré pattern, we estimate this solid angle of reflected rays and trace these rays. An image-based accelerating method is adopted so that the contribution of each reflected ray can be quickly obtained without elaborate intersection calculation. We also demonstrate anti-aliased shadows of sunlight and skylight on the water surface. Both the rendered images and animations show excellent effects on the water surface of a reservoir. The first, third and fifth co-authors were partially supported by the National Natural Science Foundation of China (Grant Nos. 60021201 and 60373035), Key Research Project of Ministry of Education (Grant No.01094) and the National Grand Fundamental Research 973 Program of China (Grant No.2002CB312102). Xue-Ying Qin is an associated professor of State Key Laboratory of CAD&CG, Zhejiang University. She received her Ph.D. degree from Hiroshima University in 2001, B.S. and M.S. degrees in Mathematics from Peking University in 1988 and from Zhejiang University in 1991, respectively. Her research interests include computer graphics, visions and image processing. Eihachiro Nakamae is currently Chairman of Sanei Co. He was granted the title of emeritus professor from both Hiroshima University and Hiroshima Institute of Technology. He was appointed as a researcher associate at Hiroshima University in 1956, a professor from 1968 to 1992 and an associated researcher at Clarkson College of Technology, Potsdam, N.Y., from 1973 to 1974. He was a professor at Hiroshima Prefectural University from 1992 to 1995 and a professor at Hiroshima Institute of Technology from a996 to the end of March 1999. He received his B.E., M.E., and Ph.D. degrees in electrical engineering in 1954, 1956, and 1967 from Waseda University. His research interests include computer graphics, image processing and electric machinery. He is a member of IEEE, ACM, CGS, Eurographics, IEE of Japan, and IPS of Japan. Wei Hua received his Ph.D. degree in applied mathematics from Zhejiang University in 2002. He joined the CAD&CG State Key Lab in 2002. His main interests include real-time simulation and rendering, virtual reality and software engineering. Yasuo Nagai is now an associate professor of Hiroshima Institute of Technology. He was appointed a researcher associate at Hiroshima Institute of Technology in 1965, and an associate professor in 1984. His research interests include computer graphics and image processing. He is a member of IEE, IEICE, IPSJ, and ITE of Japan. Qun-Sheng Peng was born in 1947. He received his Ph.D. degree in computer science from the University of East Anglia, U.K., in 1983. He is a professor and his research interests include computer graphics, computer animation, virtual reality, and point-based modeling and rendering.     

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.     

An in-depth analysis of information markets with aggregate uncertainty

The novel idea of setting up Internet-based virtual markets, information markets, to aggregate dispersed information and predict outcomes of uncertain future events has empirically found its way into many domains. But the theoretical examination of information markets has lagged relative to their implementation and use. This paper proposes a simple theoretical model of information markets to understand their information dynamics. We investigate and provide initial answers to a series of research questions that are important to understanding how information markets work, which are: (1) Does an information market converge to a consensus equilibrium? (2) If yes, how fast is the convergence process? (3) What is the best possible equilibrium of an information market? and (4) Is an information market guaranteed to converge to the best possible equilibrium? The authors acknowledge the support of the eBusiness Research Center at the Pennsylvania State University. Yiling Chen is a postdoctoral research scientist at Yahoo! Research, New York. She received her Bachelor of Economics degree in Commodity Science from Renmin University of China, in 1996, and her Master of Economics degree in Finance from Tsinghua University, China, in 1999. She worked for PriceWaterhouse Coopers China as a professional auditor from August 1999 to June 2000. From August 2000 to July 2001, she attended Iowa State University, Ames, IA, as a Ph.D. student in economics. She obtained her Ph.D. in Information Sciences and Technology from the Pennsylvania State University, University Park, PA, in 2005. Her research interests lie on the boarder of computer science, economics, and business, including information markets, auction theory, and machine learning. Tracy Mullen is an assistant professor of information sciences and technology at the Pennsylvania State University, University Park, PA. She has previously worked at Lockheed Martin, Bellcore, and NEC Research. She received her PhD in Computer Science from University of Michigan. Her research interests include information markets, multiagent systems, ecommerce, market-based resource allocation for sensor management, and supply chain simulations using intelligent agents. Her research papers have been published in Decision Support Systems, Electronic Commerce Research, IEEE Computer, ACM Transactions on Internet Technology, Mathematics and Computers in Simulation, and Operating Systems Review, among others. Chao-Hsien Chu is an associate professor of information sciences and technology and the executive director of the Center for Information Assurance at the Pennsylvania State University, University Park, PA. He was previously on the faculty at Iowa State University, Iowa and Baruch College, New York and a visiting professor at University of Tsukuba (Japan) and Hebei University of Technology (China). He is currently on leaves to the Singapore Management University (Singapore) (2005–2006). Dr. Chu received a Ph.D. in Business Administration from Penn State. His current research interests are in communication networks design, information assurance and security (especially in wireless security, intrusion detection, and cyber forensics), intelligent technologies (fuzzy logic, neural network, genetic algorithms, etc.) for data mining (e.g., bioinformatics, privacy preserving) and supply chains integration. His research papers have been published in Decision Sciences, IEEE Transactions on Evolutionary Computation, IIE Transactions, Decision Support Systems, European Journal of Operational Research, Electronic Commerce Research, Expert Systems with Applications, International Journal of Mobile Communications, Journal of Operations Management, International Journal of Production Research, among others. He is currently on the editorial review board for a number of journals.     

Information access in multimedia databases based on feature models

With the increasing popularity of the WWW, the main challenge in computer science has become content-based retrieval of multimedia objects. Access to multimedia objects in databases has long been limited to the information provided in manually assigned keywords. Now, with the integration of feature-detection algorithms in database systems software, content-based retrieval can be fully integrated with query processing. We describe our experimentation platform under development, making database technology available to multimedia. Our approach is based on the new notion of feature databases. Its architecture fully integrates traditional query processing and content-based retrieval techniques. Arjen P. de Vries, Ph.D.: He received his Ph.D. in Computer Science from the University of Twente in 1999, on the integration of content management in database systems. He is especially interested in the new requirements on the design of database systems to support content-based retrieval in multimedia digital libraries. He has continued to work on multimedia database systems as a postdoc at the CWI in Amsterdam as well as University of Twente. Menzo Windhouwer: He received his MSc in Computer Science and Management from the University of Amsterdam in 1997. Currently he is working in the CWI Database Research Group on his Ph.D., which is concerned with multimedia indexing and retrieval using feature grammars. Peter M.G. Apers, Ph.D.: He is a full professor in the area of databases at the University of Twente, the Netherlands. He obtained his MSc and Ph.D. at the Free University, Amsterdam, and has been a visiting researcher at the University of California, Santa Cruz and Stanford University. His research interests are query optimization in parallel and distributed database systems to support new application domains, such as multimedia applications and WWW. He has served on the program committees of major database conferences: VLDB, SIGMOD, ICDE, EDBT. In 1996 he was the chairman of the EDBT PC. In 2001 he will, for the second time, be the chairman of the European PC of the VLDB. Currently he is coordinating Editor-in-Chief of the VLDB Journal, editor of Data & Knowledge Engineering, and editor of Distributed and Parallel Databases. Martin Kersten, Ph.D.: He received his PhD in Computer Science from the Vrije Universiteit in 1985 on research in database security, whereafter he moved to CWI to establish the Database Research Group. Since 1994 he is professor at the University of Amsterdam. Currently he is heading a department involving 60 researchers in areas covering BDMS architectures, datamining, multimedia information systems, and quantum computing. In 1995 he co-founded Data Distilleries, specialized in data mining technology, and became a non-executive board member of the software company Consultdata Nederland. He has published ca. 130 scientific papers and is member of the editorial board of VLDB journal and Parallel and Distributed Systems. He acts as a reviewer for ESPRIT projects and is a trustee of the VLDB Endowment board.     

Linear logic for deductive databases

This paper deals with deductive databases in linear logic. The semantics of queries, views, constraints, and (view) updates are defineddeclaratively in linear logic. In constrast to classical logic, we can formalise non-shared view, transition constraints, and (view) updates easily. Various proof search strategies are presented along with an algorithm for query evaluation from a bottom-up direction. An additional advantage is that the associated meaning of a given relation can be defined in terms of the validity of a legal update in a given relation. We also defined formally the update principles and showed the correctness of the update translation algorithms. In this approach, we provide virtual view updates along with real view updates, and view DELETIONs are special cases of view REPLACEMENTs. This permits three transactional view update operations (INSERTION, DELETION, REPLACEMENT) in comparison to only (INSERTION, DELETION) in most existing systems. Dong-Tsan Lee, Ph.D.: He is a computer scientist in the Department of Computer Science at University of Western Australia, Perth, Western Australia, Australia. He received the B.S. and M.S. degrees from the Department of Computer Science at National Chiao-Tung University, Taiwan, in 1983 and 1985, respectively, and earned the Ph.D. degree from the Department of Computer Science at University of Western Australia. His research interests include database and artificial intelligence, linear logic, and real-time software engineering. Chin-Ping Tsang, Ph.D.: He is currently an associate professor in the Department of Computer Science at University of Western Australia, Perth, Western Australia, Australia. He received the Ph.D. degree from the University of Western Australia. He was the head of the Department of Computer Science at the University of Western Australia from 1994 to 1997. His research interests include artificial intelligence, non-classicial logic and neural nets.     

On the suitability of Biological structure determination by electron microscopy to Grid Computing

The present contribution describes a potential application of Grid Computing in Bioinformatics. High resolution structure determination of biological specimens is critical in BioSciences to understanding the biological function. The problem is computational intensive. Distributed and Grid Computing are thus becoming essential. This contribution analyzes the use of Grid Computing and its potential benefits in the field of electron microscope tomography of biological specimens. Jose-Jesus Fernandez, Ph.D.: He received his M.Sc. and Ph.D. degrees in Computer Science from the University of Granada, Spain, in 1992 and 1997, respectively. He was a Ph.D. student at the Bio-Computing unit of the National Center for BioTechnology (CNB) from the Spanish National Council of Scientific Research (CSIC), Madrid, Spain. He became an Assistant Professor in 1997 and, subsequently, Associate Professor in 2000 in Computer Architecture at the University of Almeria, Spain. He is a member of the supercomputing-algorithms research group. His research interests include high performance computing (HPC), image processing and tomography. Jose-Roman Bilbao-Castro: He received his M.Sc. degree in Computer Science from the University of Almeria in 2001. He is currently a Ph.D. student at the BioComputing unit of the CNB (CSIC) through a Ph.D. CSIC-grant in conjuction with Dept. Computer Architecture at the University of Malaga (Spain). His current research interestsinclude tomography, HPC and distributed and grid computing. Roberto Marabini, Ph.D.: He received the M.Sc. (1989) and Ph.D. (1995) degrees in Physics from the University Autonoma de Madrid (UAM) and University of Santiago de Compostela, respectively. He was a Ph.D. student at the BioComputing Unit at the CNB (CSIC). He worked at the University of Pennsylvania and the City University of New York from 1998 to 2002. At present he is an Associate Professor at the UAM. His current research interests include inverse problems, image processing and HPC. Jose-Maria Carazo, Ph.D.: He received the M.Sc. degree from the Granada University, Spain, in 1981, and got his Ph.D. in Molecular Biology at the UAM in 1984. He left for Albany, NY, in 1986, coming back to Madrid in 1989 to set up the BioComputing Unit of the CNB (CSIC). He was involved in the Spanish Ministry of Science and Technology as Deputy General Director for Research Planning. Currently, he keeps engaged in his activities at the CNB, the Scientific Park of Madrid and Integromics S.L. Immaculada Garcia, Ph.D.: She received her B.Sc. (1977) and Ph.D. (1986) degrees in Physics from the Complutense University of Madrid and University of Santiago de Compostela, respectively. From 1977 to 1987 she was an Assistant professor at the University of Granada, from 1987 to 1996 Associate professor at the University of Almeria and since 1997 she is a Full Professor and head of Dept. Computer Architecture. She is head of the supercomputing-algorithms research group. Her research interest lies in HPC for irregular problems related to image processing, global optimization and matrix computation.