Applications

See also the MGS Graphic Gallery

• Why developping “unconventionnal programming languages”: Challenging Questions for the Rationals of Non-Classical Programming Languages article published in IJUC Vol. 2, N° 4, 2006, pp. 337-347 (preliminary version)

• On the topological perspective on programming: Topological rewriting and the geometrization of programming. Physica D, 237:1302–1314, 2008.

Unconventional Programming Paradigms
International Workshop UPP 2004, Le Mont Saint Michel, France, September 15-17, 2004, Revised Selected and Invited Papers. Series: Lecture Notes in Computer Science , Vol. 3566
editors: Jean-Pierre Banâtre, Pascal Fradet, jean-Louis Giavitto, Olivier Michel.

2005, XI, 367 p. With online files/update., Softcover. ISBN: 978-3-540-27884-9
Initial NFS Report

Molecular Computational Models - Unconventional Approaches
chapter : Modeling Developmental Processes in MGS
edited by Marian Gheorghe (Univ. of Sheffield)
2005, 287 pages, ISBN: 1-59140-334-0 Table of Content

Systems Self-Assembly: multidisciplinary snapshots
chapter: Simulation of self-assembly processes using abstract reduction systems
edited by Natalio Krasnogor, Steve Gustafson, David Pelta and Jose L. Verdegay
2008, 304 pages, ISBN-10: 0-444-52865-2
table of contents

The chemical computing model describes computation as the reaction between “molecules” (data) floating in a “chemical soup”. It can be formalized as commutative-associative rewriting. Chemical computing includes several threads or researches:

• Gamma was introduced in 1986 by JP Bânatre and D. Le Metayer as a formalism for the definition of programs without artificial sequentiality. The basic idea underlying the formalism is to describe computation as a form of chemical reaction on a collection of individual pieces of data.
  • Gamma and the chemical reaction model
  • Gamma And The Chemical Reaction Model: Ten Years After
  • Gamma and the chemical reaction model: Fifteen years after
  • The papers of J.-P. Bânatre
  • The original definition of Gamma does not provide any facility for data structuring or for specifying particular control strategies. Structured Gamma address this issue by introducing a notion of structured multiset which is a set of addresses satisfying specific relations. The relations can be seen as a form of neighborhood between the molecules of the solution; they can be used in the reaction condition of a program or transformed by the action. Structured Gamma introduces the typing of these structured multi set by a context-free graph grammar. Science of Computer Programming 31(2-3), pp. 263-289, 1998. (Preliminary version).
  • Another notable evolution is of Gamma is HOCL which introduces higher-order by making the rules, first-order molecules.
    • The thesis (in french) of Yann Radenac
    • Programming Self-Organizing Systems with the Higher-Order Chemical Language. IJUC, 3(3):161-177, 2007. (preprint version)

• CHAM, the chemical abstract machine has been developped around 1992 by Berry and Boudol as a formalism to describe the semantics of asynchronous parallel processes. A more recent follow-up is the join-calculus a language that models distributed and mobile programming. It is characterized by an explicit notion of locality, a strict adherence to local synchronization, and a direct embedding of the ML programming language. The join calculus is used as the basis for several distributed languages and implementations, such as JoCaml and functional nets.

• When usd in parallelism, the multiset (the “chemical solution”) is viewed as a distributed data structure. This approach extends to view the internet as a chemical solution. Thus, the chemical metaphor has spawned a number of researches in web services and coordination languages. For instance:
  • the works of Priol and Tedeschi group at IRISA
  • the work of Viroli, Zambonelli and collegues (here is an example

• P systems and Membrane Computing extend the chemical computing metaphor with nesting: inspired by biological membranes, the chemistry is now encapsulated in nested membranes and additional rules are used to move the molecules between the membranes. The focus is definitively on formal languages and calculability/complexity theory but in the last years, P systems formalisms have been used in biological modeling. The P systems Webpage is a good entry point. The following MGS publications are related to Membrane Computing:
  • The topological structures of membrane computing. Fundamenta Informaticae, 49:107–129, 2002.
  • Accretive rules in Cayley P systems (LNCS 2597)
  • Stochastic p systems and the simulation of biochemical processes with dynamic compartments. BioSystems, 91(3), 2008. bib pdf

• Organic computing is a form of biologically-inspired computing with organic properties. It has emerged recently as a challenging vision for future information processing systems. Chemical programming has been advocated for organic computing: The Chemical Metaphor as Programming Paradigm for Organic Computing

• Artificial Chemistry focuses on the algorithms induced by the chemical metaphor. Check this review (2001) by Peter Dittrich and others.

• Real chemistry is actually used to perform computations. See for instance the home page of Andy Adamatzky, the NeuNeu project and the web page of the COBRA coordination action of the BioChemIT of the European Commision.

Lindenmayer systems are a kind of string rewriting where rule application occurs in parallel. The have been introduced by A. Lindenmayer for modeling plant growing. But they have attracted the attention of computer scientist because despite their similarity with Chomsky grammar, their complexity hierarchy is different. They are two main streams of researches:

• Modeling in botany, see the Algorithmic Botany website of the P. Prusinkiewicz's group (the visualization of the corrresponding structure is also a concern here).
• Formal languages and theoretical computer science (cf. for instance the book Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology

DOL System are straightforward to program in MGS using transformation on a sequence of symbols. Context sensitive L systems are more tricky to achieve using a sequence of symbols because the context (the neighborhood) take into account the parenthesis in the sequence. It is then better to use trees. Tree can be achieved in MGS using nesting or graphs.

• Fraglets are tiny computation fragments or tokens that flow through a computer network. Fraglets implement a chemical reaction model where computations are carried out by having fraglets “react” with each other. Fraglets can be used to explore new protocol engineering and implementation opportunities.

* An MGS emulation of fraglets.

• A topological framework for the specification and the simulation of discrete dynamical systems. International conference on Cellular Automata for Research and Industry (ACRI'04), LNCS 3305, 2004. (preprint)

The Blob computing project is developped at the U. of Paris-Sud by F. Gruau. A Blob is a generic primitive used to structure a uniform computing medium into an easier-to-program parallel virtual machine: a Self Developping - self mapping network of automata.

Blob movement and collision using a physical model has been done in MGS by Julien Cohen. The model relies on real coordinate and two kinds of particles: membrane particles with an attractive force between neighbors, and gas particles, with a repulsive force. We illustrate two chocs: a frontal choc where blobs bounce horizontally, and a “side” choc where they bounce at right angle.

• The proto home page

• Spatial Computing as Intensional Data Parallelism at SCW 2009. (slides)

MGS has been used to explore the state space of a standard prtocol (NSPK) and to find an error. Altough this is a simple and well known example, it shows the MGS ability to build and explore abstract space for verification purposes (model-checking).

There are some research in the verification of MGS program, or at least, some subset.

A version of Three variations on the analysis of the Needham-Schroeder Public-Key Protocol with MGS has been published as a chapter in a book on the Application of membrane computing.

A interesting feature of the approach is the use of multiset of partially applied function to represent the traces of the protocol.

In http://example.com|Integrated Regulatory Networks (IRNs): Spatially organized biochemical modules, we aim at modeling and analyzing the regulation processes in multi-cellular biological systems, in particular, tissues. The modeling framework is a generalization of several existing formalisms. In particular, it can be seen as an extension of logical regulatory networks (à la Thomas) with information about cells’ physical state and environment, e.g., their spatial relationships. The resulting formalisms, called integrated regulatory networks (IRNs) is equipped with a transition systems semantics that preserves the possibility of an enumerative and exhaustive state space exploration. This paper presents the modeling framework, its semantics, as well as a prototype implementation that allowed preliminary experiments on some applications related to biology.

The work is published in TCS. A preliminary version is available here.

• Checjk the chapter Simulation of self-assembly processes using abstract reduction systems in the book Systems Self-Assembly: multidisciplinary snapshots edited by Natalio Krasnogor, Steve Gustafson, David Pelta and Jose L. Verdegay, Elsevier, 2008.

• Declarative modeling of a neurulation-like process. BioSystems, 2006.

1. The modelling with MGS of the Paris iGEM'2007 project is detailed in Understanding the Dynamics of Biological Systems: Lessons Learned from Integrative Systems Biology (Springer). A preliminary version is available here.

1. The Modeling and the Simulation of the Fluid Machines of Systems/Synthetic Biology at http://cmc12.lacl.fr/CMC'2011 (slides).

1. The SynBioTIC project (in french)

1. Spatial computing and cell programming: the PROTO approach

• Computer simulations reveal properties of the cell-cell signaling network at the shoot apex in Arabidopsis (PNAS 2005)
• The corresponding thesis of Pierre Barbier de Reuille.

• Spatial Programming for Music Representation and Analysis, SCW 2010.

• Building Topological Spaces for Musical Objects, Mathematics and Computation in Music. Paris, LNCS 6726, 2011.