Pisa - Dipartimento di Informatica - Research Evaluation Exercise 1999

The Logic
Molecule Manipulation Systems

Proposer: Vincenzo Manca


The research intends to develop a logical analysis of string manipulation systems which provides: i) a unification of many formalisms (e.g. Unregulated and Regulated Classical Systems, Grammar Systems, L-systems, H-systems, P-systems), and ii) the definition of a framework for the investigation of complex discrete dynamic systems inspired by chemical and biochemical processes.

State of the Art and Trends

In the field of DNA Computing, which represents one of the most innovative proposals among the emergent computation models, it was discovered that classical problems in the theory of formal languages show a new relevance in the perspective of systems typical in the elaboration of biological information (DNA, RNA, Protein Synthesis). In fact, operations on symbolic strings can be performed by means of DNA strands in order to solve combinatorial problems with tecniques of Genetic Engineering (cfr. Adleman's Experiment on Hamiltonian paths determined by test tube manipulations). The following words of Adleman [1] are a compact formulation of the great expectations concerning DNA computing.

``For the long term, one can speculate about the prospect for molecular computation. It seems likely that a single molecule of DNA can be used to encode the instantaneous description of a Turing machine and that currently available protocols and enzymes could (at least under idealized conditions) be used to induce successive sequence modifications, which would correspond to the execution of the machine. In the future, research in molecular biology may provide improved techniques for manipulating macromolecules. Research in chemistry may allow for the development of synthetic designer enzymes. One can imagine the eventual emergence of a general purpose computer consisting of nothing more than a single macromolecule conjugated to a ribosomelike collection of enzymes that act on it."

The recent international conferences devoted to this subject, and the relative publications in important scientific series (Springer-Verlag, Gordon and Breach, John Wiley), tell us the increasing interest in this field for the scientific community.

In the last years, the proposer introduced a logical approach [8,9,10] that seems to be adequate for the unification of classical and recent symbolic formalisms. This approach could help in discovering general principles that are common to artificial systems 'in info', and to natural systems 'in vitro' and 'in vivo'. In this perspective, theoretical instruments of Computer Science (Languages, Grammars, Automata,Formal Systems) could become essential tools in the formal analysis and in the prediction for dynamic discrete systems of natural processes, where, very often, the classical instruments of classical mathematics are inadequate or even impossible to be applied.

Short Term Plans and Expected Results:

In the recent years many computation formalisms have emerged that are based on the notion of formal grammar or, more generally, of string rewriting. In fact, the grammatical paradigm seems a very natural way to provide new models for expressing phenomena such as parallelism, cooperation, and distribution. Furthermore, string rewriting has become a formal tool in the description of developmental phenomena of biological organisms, after Lindenmayer introduced L-systems with their main variants, (E)OL, (E)DOL, (E)TOL, (E)IL, based on the parallel rewriting mechanism (the importance of L-systems in computer graphics and Fractal Representation is a more recent application of this theory).

More recently, grammatical models have been elaborated in the field of 'artificial life' for the simulation of aspects of life such as: birth, growth, death, reproduction, evolution, proliferation, stagnancy and pollution. Other important possibilities of an interaction between formal languages and biology arise from molecular biology models of DNA and from their applications in solving combinatorial problems (Adleman's experiment), and in suggesting new patterns of string rewriting, inspired by genetic elaboration of cellular information: Splicing and H-systems introduced by Head in 1987, which constitute the kernel of DNA Computing. If we consider the original context of Kleene's theorem about regular languages (published in a paper entitled "Representation of events in nerve nets and finite automata"), we realize the importance and the persistency of biological contents in the evolution of Formal Language Theory.

All the types of grammars, automata, and symbolic systems (with all their combinatorial patterns, regulation mechanisms, and derivation strategies) constitute an enormous number of different systems with a tremendous variety of generative power and a very wide spectrum of expressive possibilities. We project to develop an intensional analysis of these systems in a logical framework which extends an approach, introduced in our previous works, essentially based on the notion of monoidal theory. The attribute 'intensional' is used in opposition to the classical 'extensional' analysis; this is essentially focused on the languages that systems generate and on the localization of these languages in Chomsky's hierarchy, or in other hierarchies.

An intensional study of string manipulation systems is naturally connected with a logical formalization of them, and could suggest guidelines in the formal analysis of more general forms of discrete dynamic systems which arise in physical, chemical, biochemical, or biological contexts. In this more general perspective, the analysis of symbolic systems requires not only the representation of generation and development, but also of: aggregation, locality, osmosis, permeability, encapsulation, termination, determinism, stability, periodicity, and interactivity (synergy, antagonism, resonance). Formal languages, and more specifically DNA Computing, for their centrality in representation and computation, seem to be the natural setting where new mathematical models can be found which are adequate to study complex, discrete dynamics.

On the other hand, DNA Computing could represent the natural setting where implement the passage: 'From Silicon to Carbon', that is, 'From microchips to DNA molecules' where the information-processing capabilities of organic molecules could be used to replace digital switching primitives. This objective is of course of experimental nature and though it is outside our aims, it could greatly influence our ideas, and at same time, be influenced by our results in mathematical representation of discrete dynamic systems (some laboratories of DNA Computing, one of them in Europe, are involved with experiments of test tube generation of languages).

In a first approximation, symbolic molecules can be equated to strings; neverthless, in specific cases strings have to be equipped with some extra structure (e.g. double strands, multisets, localization, types,...) in order to express important peculiarities of real molecule systems. One possibility of structuring strings is the notion of 'membrane' for expressing phenomena of aggregation, localization and filtering. Recently, several proposals were elaborated in this direction within the mathematical framawork of P-systems. We want investigate on logical theories where these phenomena can be axiomatically expressed indipendently from the combinatorial mechanism of the underlying symbolic system (replacement, splicing, insertion-deletion).

Short Bibliography

1) L. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266, 1021-1024, 1994.

2) E. Csuhaj-Varju, J. Dassow, J. Kelemen, G. Paun, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.

3) J. Dassow, Gh. Paun, On the power of membrane computing, J. Of Universal Computer Sci., 5, 2 (1999), 33-49.

4) T. Head, Formal Language Theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Bullettin of Mathematical Biology, 49, 737-759, 1987.

5) V. Manca, G. Paun, Arithmetically controlled H systems, Computer Science Journal of Moldova, N. 2, pp. 22-33, 1998.

6) V. Manca, C. Martin-Vide, G. Paun, New Computing Paradigms Suggested by DNA Computing: Computing by Carving, in: Biosystems, Special Issue devoted to the 4th DIMACS Meeting on DNA Based Computing, L. Kari, H. Rubin, D.H. Woods (eds.), Pennsylvania Univ.,June 15-19, pp. 41-56, Philadelpia, 1998.

7) V. Manca, C. Martin-Vide, G. Paun, Iterated GSM Mappings: A Collapsing Hierarchy, Turku Centre for Computer Science, TUCS Technical Report N. 206, (to appear in a Springer Series), 1998.

8) V. Manca, String Rewriting and Metabolism: A logical perspective, in Computing with Bio-Molecules, Volume: 7, pp. 36-60, Paun G. (ed.), Series in Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, Singapore, 1998.

9) V. Manca, Logical String Rewriting and Molecular Computing, accepted for publication in Theoretical Computer Science, Special Issue devoted to MFCS 98, 23rd International Symposium on Mathematical Foundations of Computer Science, 1998.

10) V. Manca, From String Rewriting to Logical Metabolic Systems, Volume: 8, pp.: 297-315, Paun G., Salomaa A. (eds.), Topics in Computer Mathematics, Gordon and Breach Science Publishers, London, 1999.

11) V. Manca, Logical Splicing in Natural Languages, MFCS 98, 23rd International Symposium on Mathematical Foundations of Computer Science, Satellite Workshop on Mathematical Linguistics,Brno, August, 23-28, 1998.

12) G. Paun, G. Rozenberg, A. Salomaa, DNA Computing, Springer-Verlag, 1998.

13) G. Paun (ed.), Computing with Biomolecules, Springer-Verlag, 1998.

14) G. Paun, A. Salomaa (eds.), Grammatical Models of Multi-Agent Systems, Gordon and Breach,1999.

15) G. Paun, Computing with membranes, Turku Center for Computer Science-TUCS Report No 208, 1998.

16) G. Paun, Computing with membranes. An introduction, Bulletin of the EATCS, 67 (Febr. 1999), 139-152.

17) G. Paun, G. Rozenberg, A. Salomaa, Membrane computing with external output, Turku Center for Computer Science-TUCS Report No 218, 1998.

18). G. Paun, Y. Sakakibara, T. Yokomori, P systems on graphs of restricted forms, manuscript, 1999.

19) G. Paun, G. Thierrin, Multiset processing by means of systems of sequential transducers, Auckland University, CDMTCS Report No 101, 1999.

20) G. Paun, T. Yokomori, Membrane computing based on splicing, manuscript, 1999.

21) I. Petre, A normal form for P systems, Bulletin of the EATCS, 67 (Febr. 1999), 165-172.

22) G. Rozenberg, A. Salomaa, Handbook of Formal Languages, 3 Voll., Springer-Verlag, 1997.

Long Term Scenarios:

A biological system is constituted, at any level, by a physico-chemical support and by an information system that regulates the life processes, according to different strategies (phylogenetic, ontogenetic, epigenetic), for general finalities (fitness, reproduction, evolution), and for specific functionalities of the organisms. The discovery of the discrete informational nature of the basilar life processes gives to theoretical computer science, and especially to the theory of formal languages, a priviliged status in the formal analysis of the crucial phenomena of organic reality.

A long term application of our approach is the analysis of real phenomena of biological processes based on the elaboration of discrete information (DNA, Protein synthesis, metabolisms). In this perspective, general theories of molecule systems could provide mathematical models which explain principles, peculiarities, and dysfunctions hardly understandable in the traditional informal frameworks.

Short CV:

Vincenzo Manca received M.Sc. in Mathematics from University of Pisa in 1971. Then, he was Fellowship (C.N.R. and of Italian Ministry for Education) in Mathematical Logic and Computing Theory. In 1989 he became 'Prof. Associato' and since 1992 he is 'Prof. Associato' at Departmemt of Computer Science in the University of Pisa where he teachs courses in Mathematical Logic and Computability Theory.

His interests include: Mathematical Logic (Algebraic and Equational Logic in semantics of Programming Languages), Computational Models and Formal Languages (Combinators and Abstract Computability, recently DNA and Molecular Computing), and Natural Language Logic. He is member of E.A.T.C.S. (European Associaton for Theoretical Computer Science), and A.M.S. (Americam Mathematical Society), and New York Academy of Sciences. He has been 'Visiting Professor' in many Universities and International Institutions (Budapest, Enschede, Tarragona, Limerick). He is author of about sixty scientific papers and books, many of which appear in international journals and series: Notre Dame Journal of Formal logic, Fundamenta Informaticae, Theoretical Computer Science, Biosystems, Colloquia Mathematica Societatis Janos Bolyai, Institute of Mathematics and its Applications, Lecture Notes in Computer Science (Springer-Verlag), Series in Discrete Mathematics and Theoretical Computer Science (Springer-Verlag), Series on Topics in Computer Mathematics (Gordon and Breach), Series on Studies in Functional and Structural Linguistics (John Benjamins & Sons), Encyclopedia of Electrical and Electronics Engineering (John Wiley & Sons), Studi di Grammatica Italiana (Accademia della Crusca), Societa` Linguistica Italiana. He is referee for several international scientific Journals and is local coordinator of national research projects.

Proposer's Publications (5):

1) V. Manca, A. Salibra, G. Scollo, Equational Type logic, Theoretical Computer Science, 77, 1-29, 1990.

2) V. Manca, A. Salibra, Soundness and completeness of the Birkhoff equational calculus for many-sorted algebras with possibly empty carrier sets, Theoretical Computer Science, 94 (1), 101-124, 1992.

3) V. Manca, A Metagrammatical Logical Formalism, in: Mathematical and Computational Analysis of Natural Language, in: Carlos Martin-Vide (ed.), Studies in Functional and Structural Linguistics, Vol. 45, pp. 145-158, John Benjamins Publishing Company Amsterdam, 1998.

4) V. Manca, String Rewriting and Metabolism: A Logical Perspective, in: Paun G. (ed.), Computing with Bio-Molecules, Volume: 7, pp.: 36-60, Series in Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, Singapore, 1998.

5) V. Manca, From String Rewriting to Logical Metabolic Systems, in: Paun G., Salomaa A. (eds.), Volume: 8, pp.: 297-315, Topics in Computer Mathematics, Gordon and Breach Science Publishers, London, 1999.


1) Erzsebet Csuhaj-Varju, Hungarian Academy of Sciences, Budapest, Hungary;

2) Carlos Martin-Vide, Rovira i Virgili University of Tarragona, Spain;

3) Gheorge Paun, Institute of Mathematics of the Romanian Academy, Bucuresti, Romania.


Computation Models, DNA Computing, Formal Languages, Formal Systems, Logical Theories.

Index Page