back to the tutorial home page
back to the MGS home page

Applications

See also the MGS Graphic Gallery


Programming Unconventionnal Models

  • 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)



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









couverture.jpg

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









couverture2.jpg
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



Rewriting based

Chemical Computing: Gamma, HOCL, P systems

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.
    • 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.
  • 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:
  • 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:
  • Artificial Chemistry focuses on the algorithms induced by the chemical metaphor. Check this review (2001) by Peter Dittrich and others.



Lindenmayer systems

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:

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.

Fraglet

  • 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.



Non-rewriting based

Cellular and Lattice gaz automata

  • 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)

Blob computing

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.

Proto

Data parallelism

Transition Systems and Verifications

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.

The Needham-Schroeder public-key protocol

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.

Integrated Regulatory Network (IRN)

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.



Self-assembly



Biology

Gastrulation

Synthetic Biology

The Growth of a Meristem

Music

Artificial Intelligence

Extracting an Ontology without a priori : The Little Red Riding Hood

Analogy through paths


Personal Tools