Our recent research concentrates on the following main topics: test tube systems, computational paradigms based on Watson-Crick complementarity, and P systems (P automata).

Test tube systems are distributed communicating systems built up from computing devices (test tubes) based on operations motivated by the recombinant behaviour of DNA strands. These operations are applied to the objects in the test tubes (strings) in a parallel manner and then the results of the computations are redistributed according to certain specified criteria (input/output filters associated with the components) which allow only specific parts of the contents of the test tube to be transferred to the other tubes. In cooperation with Lila Kari and Gheorghe Paun, we introduced and studied properties of test tube systems based on splicing [2], and in cooperation with Rudolf Freund and Franz Wachtler we defined and examined test tube systems based on cutting and recombination operations [3]. Both models proved to be as powerful as Turing machines, giving a theoretical proof of the possibility to design universal programmable computers with distributed architectures of biological computers based on DNA molecules. These results are important developments of our results in [1].

Main questions in the research in models of test tube system are - among other things - comparisons of the variants with different basic operations motivated by the behaviour of DNA strands or DNA-related structures according to their computational power, programmability, simplicity of the filters, topology of the test tubes, approachability of intractable problems. Our investigations follow this line.

At present we explore test tube systems with multisets of objects (symbols, strings, data structures) and operations modelling biochemical reactions [6]. In addition to the computational power, the emphasis is put on elaborating complexity notions for these devices.

An other important direction of our research is to study language theoretical models motivated by Watson-Crick complementarity, a fundamental concept in DNA Computing. A paradigm, where Watson-Crick complementarity is viewed in the operational sense, was proposed for further considerations by Valeria Mihalache and Arto Salomaa in 1997.

According to the proposed model, a "bad" string (a string satisfying a specific condition, a trigger) produced by a generative device induces a complementary string either randomly or guided by a control device. The concept can also be interpreted as follows: in the course of a developmental or computational process, things can go wrong to such an extent that it is advisable to switch to the complementary string, which is always available.

In close cooperation with Arto Salomaa (Turku Centre for Computer Science), we study properties of Watson-Crick DOL systems, a variant where the underlying generative device is a DOL systems, a parallel string rewriting mechanism modelling developmental systems. In the frame of our joint research, we have introduced and now explore networks of Watson-Crick D0L systems, where communication among the Watson-Crick D0L systems at the nodes is controlled by the trigger for turning to the complementary ([5], [4], [7]). We study the power of these constructs (which proved to be computationally complete in the case of certain variants), and we have achieved interesting results in describing the dynamics of string collections found at the nodes.

In [10] we established three results about the power of such networks. Two of them show how it is possible to solve in linear time well-known NP-complete problems, the Hamiltonian Path Problem and the Satisfiability Problem. The third one shows how in the very simple case of four-letter DNA alphabets we can obtain weird (not even Z-rational) patterns of population growth. We expect further research and cooperation in this field in the future.

In the area of P systems, we introduced a new notion, called P automaton, [9], which is a construction realizing an accepting variant of P systems, and proved that P automata are as powerful as the Turing machines. The concept provided membrane computing with a new approach and at the same time built a bridge between the scientific field of P systems and automata theory. The notion received immediate attention, since its first presentation in August, 2002 at the workshop "Membrane Computing", Curtea de Arges.

References

[1]

E. Csuhaj-Varjú, R. Freund, L. Kari and Gh. Paun: DNA Computing Based on Splicing: Universality Results. In: Pacific Symposium on Biocomputing'96. Ed. by L. Hunter and T. E. Klein, World Scientific, Singapore, 1996, 179-190.

[2]

E. Csuhaj-Varjú, L. Kari and Gh. Paun: Test Tube Distributed Systems Based on Splicing. Computers and Artificial Intelligence 15(2) (1996), 211-232.

[3]

R. Freund, E. Csuhaj-Varjú and F. Wachtler: Test Tube Systems with Cutting/Recombination Operations In: Pacific Symposium on BIOCOMPUTING'97. Ed. by R.B. Altman et al., World Scientific, Singapore, 1997, 163-175.

[4]

E. Csuhaj-Varjú: Computing by networks of standard Watson-Crick D0L systems. In: Proc. Workshop on Algebraic Systems, Formal Languages and Computations, Kyoto, 21-23 March, 2000. Ed. by M. Ito, to appear.

[5]

E. Csuhaj-Varjú and A. Salomaa: Networks of Watson-Crick D0L systems. Presented at 3rd Int. Colloquium on Words, Languages and Combinatorics, March 14-18, 2000, Kyoto. Submitted to the proceedings.

[6]

E. Csuhaj-Varjú and Gy. Vaszil: Objects in Test Tube Systems In: Pre-Proceedings of the Workshop on Multiset Processing, Curtea de Arges, Romania, 21-25 August, 2000. Eds. by C.S. Calude, M.J. Dinneen and Gh. Paun, Research Report Series of the Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, No. 140, 2000, 68-77.

[7]

E. Csuhaj-Varjú: On Language-theoretic Aspects of Watson-Crick Complementarity: Models and Results. In: Proc. Theorietag 2000 mit Workshop New Computing Paradigms: Molecular Computing and Quantum Computing, Vienna, 25-27 September, 2000. Ed. by R. Freund, Technische Universität Wien, 2000, 11-33.

[8]

E. Csuhaj-Varjú and Gy. Vaszil: Research in Theoretical Foundations of DNA Computing. ERCIM News 43 (2000), 37-38.

[9]

E. Csuhaj-Varjú and Gy. Vaszil: P automata. In: Pre-Proceedings of the Workshop on Membrane Computing, Curtea de Arges, Romania, August 19-23, 2002,, edited by C. Zandron and Gh. Paun, Publication No. 1, MolCoNet-IST-2001-32008, 2002, pages 177-192.

[10]

E. Csuhaj-Varjú and A. Salomaa: The power of networks of Watson-Crick D0L systems. Submitted.