One of the goals of research in bio-inspired computing is to create new and powerful computational paradigms based on the study of the structure and behaviour of living systems. The investigations can be based on different mathematical disciplines. The Theoretical Computer Science Research Group of SZTAKI aims to expand the classic fields of automata and formal languages to explore the limits of syntactical approaches in describing natural systems.
One major characteristics of living systems is the distributed organization of their components. For this reason, our investigations concentrate on distributed bio-inspired computational models. We enhance the tools and techniques provided by formal language and automata theory with novel elements to obtain computational models which could help to provide a better understanding and a more precise description of the theoretical principles, the driving forces behind natural processes.
We are interested in both classical and unconventional characteristics of the obtained computational paradigms: their computational, descriptional, and communication complexity, their robustness, the patterns and dynamics of their behaviour, and the dependence of these properties on the structure, organization and functioning of the system.
In recent years, a significant amount of research has been devoted to membrane systems or P systems, constructs abstracted from the architecture and development of the living cell, first introduced by Gheorghe Paun in 1998. The basic variant of these systems consists of structures of hierarchically embedded membranes that delimit regions which contain objects. The objects correspond to molecules or chemical elements which evolve according to evolution rules, or move from region to region according to communication rules.
Re-considering the concept of automata, we have defined P automata, purely communicating accepting P systems which combine characteristics of both classical automata and distributed natural systems. P automata resemble classical automata in the sense that in each computational step they receive input from their environment, and this input influences their operation. What makes them different from classical automata is that the workspace that they can use for computation is provided by the objects of the already consumed input. The objects which enter the system become, in a sense, part of the description of the machine, that is, the input, the object of computation and the device which executes the computation cannot be separated. This is a feature that can usually also be observed if we interpret natural processes as "computations". Thus, in this sense P automata can be considered as a type of "natural automata".
We have characterized several classical language classes in terms of P automata. In cooperation with Oscar H. Ibarra, we determined variants which are alternatives of a Turing machine. One of these gives a "natural" representation of the class of context-sensitive languages, well-known in classical formal language theory. In a joint work with Jürgen Dassow, we have also provided a natural extension of the notion of regular languages and that of finite automata for the case of infinite alphabets.
Figure 1: A Network of Bio-inspired Language Processors. The nodes process multisets of strings and communicate with each other.
In the future, we plan to perform investigations in the theory of P automata in several directions, to make the resemblances and the differences between classical automata and P automata more explicit.
Another important focus of our research is the study of networks of bio-inspired language processors. These constructs consist of bio-inspired rewriting systems (language processors) which operate on sets or multisets of words and are located at nodes of a virtual graph. The processors use their operations to rewrite the collection of words at the nodes and then redistribute the resulting strings according to the communication protocol assigned to the system.
Due to their possible practical relevance, constructs based on operations inspired by the behaviour or properties of DNA strands are particularly important. One of the first models was the test tube sytems based on splicing (our joint work with Lila Kari and Gheorghe Paun). Through this research we have shown that several other variants of these constructs offer alternatives to Turing machines even with minimal size: networks with components based on an operation that mimics the Watson-Crick complementarity phenomenon of DNA strands (in cooperation with Arto Salomaa), or with components based on splicing and filters inspired by the laboratory technique called gel electrophoresis (in cooperation with Sergey Verlan).
Recently, we have been studying networks of evolutionary processors, where the operations are formal language theoretic counterparts of point mutations, evolution of the genome, i.e. insertion, deletion, and substitution. Our main future goals in the area include the exploration of the ''limits'' of these simple, basic operations, the identification of the cornerstones and borderlines between decidability and undecidability. In cooperation with Artiom Alhazov, Carlos Martín-Vide, Victor Mitrana and Yurii Rogozhin, we have demonstrated that these distributed systems of very simple computing devices may possess the computational power of Turing machines, even with networks and components of very small size.
Via properties of changing string collections, in the framework of networks of bio-inspired language processors, population dynamics, behavioural patterns and motifs can also be studied, thus new directions for language-theoretic approaches can be opened. In the case of networks with deterministic Lindenmayer systems as components (models of developing systems), initial results have been obtained (in cooperation with Arto Salomaa). We plan to explore these topics in the future.
The group is in close cooperation with members of the European Molecular Computing Consortium; the investigations are supported by the Hungarian Scientific Research Fund, OTKA, Grant no. K75952.
Links:
P automata: http://www.scholarpedia.org/article/P_automata
P systems webpage: http://ppage.psystems.eu
Theoretical Computer Science Research Group: www.sztaki.hu/tcs
Please contact:
Erzsébet Csuhaj-Varjú
SZTAKI, Hungary
Tel: +36 1 279 6139 begin_of_the_skype_highlighting +36 1 279 6139 end_of_the_skype_highlighting
E-mail:
György Vaszil
SZTAKI, Hungary
Tel: +36 1 279 6121 begin_of_the_skype_highlighting +36 1 279 6121 end_of_the_skype_highlighting
E-mail:
