Home page


Conference Venue
14th International Conference on Rewriting Techniques and Applications
Valencia, Spain, June 9-11, 2003


A Logical Algorithm for ML Type Inference
David McAllester (Toyota Technological Institute at Chicago, USA)

This paper gives a bottom-up logic programming formulation of the Hindley-Milne r polymorphic type inference algorithm. We show that for programs of bounded order and arity the given algorithm runs i n O(n \alpha(n) + d n) time where n is the length of the program, d is the "scheme depth" of the program, and \alpha is the inverse of Ackermann's function. It is argued that for practical programs d will not exceed 5 even for programs with hundreds of module layers. This formulation of the Hindley-Milner algorithm is intended as a case study in "logical algorithms", i.e., algorithms presented and analyzed as bottom-up inference rules.

Topological Collections, Transformations and their Application to the Modeling and the Simulation of Dynamical Systems
Jean-Louis Giavitto (Université d'Évry -- GENOPOLE, Évry, France)

I take the opportunity given by this invited talk to promote two ideas: (1) a topological point of view can fertilize the notion of rewriting and (2) this topological approach of rewriting is at the core of the modeling and the simulation of an emerging class of dynamical systems (DS): the DS that exhibit a dynamical structure (or DS2 in the rest of this paper).

This presentation is based upon the results of two research projects, 81/2 and MGS, that I have pursued hand in hand with Olivier Michel. The results and software tools presented here belong also to him and have been elaborated thanks to our long and fruitful collaboration.

Symbolic Systems Biology
Patrick Lincoln (SRI International, Menlo Park, USA)

Technological breakthroughs have enabled complete genomic sequencing and proteomic study of many species, fueling exponential growth in the available biological data relevant to important biological functions. The computational analysis of these datasets has been hampered by many structural and scientific barriers. The application of symbolic toolsets borrowed from the term rewriting and formal methods communities may help accelerate biologists understanding of network effects in complex biochemical systems of interest.

Unlike traditional biology that has focussed on single genes or proteins in isolation, systems biology is concerned with the study of complex interactions of DNA, RNA, proteins, information pathways, to understand how they work together to achieve some effect. Most systems biology research has focussed on stochastic or differential equation models of biological systems, but lack of knowledge of crucial rate constants reduces the utility of these approaches.

Symbolic Systems Biology, the application of highly automated symbolic tools such as multiset rewriting engines, model checkers, decision procedures, and SAT solvers to systems biology, attempts to leverage what is already known about biochemical systems to accelerate biological understanding. We have developed a toolset called Pathway Logic based on Maude and other symbolic tools, and applied it to signaling and metabolic pathway analysis. Pathway Logic builds on efficient pathway interaction data curation, and enables animation of complex pathway interactions, and in-silico gene knockout experiments. We have also developed methods to automatically analyze "inherently continuous" or hybrid continuous- discrete systems, creating completely symbolic representations which enable extremely efficient analysis of certain types of questions. By constructing an algebra and logic of signaling pathways and creating biologically plausible abstractions, the goal of Symbolic Systems Biology is to provide the foundation for the application of high-powered tools which can facilitate human understanding of complex biological signaling networks, such as multi-cellular signaling, bacterial metabolism and spore formation, mammalian cell cycle control, and synthetic biological circuits.

These tools will be connected to publicly available datasources and toolsets including the BioSPICE platform (available through biospice.org) which provides an interoperable service architecture for integrating model builders, simulators, experimental data repositories, and various analyzers.


Last update Apr 2003 # sescobar@dsic.upv.es