Current project
-
Nature-motivated computational modles in the theory of formal
languages and automata,
Hungarian Scientific Research Fund,
"OTKA", K 75952, 2008-2012
Project leader: E. Csuhaj-Varjú, participant: Gy. Vaszil
Background. One of the aims of research in nature-motivated computing is to create new and powerful computational paradigms based on the study of the structure and the functioning of natural systems. The scientific area includes several different research fields, for example, molecular computing, cellular computing, or artificial life. Investigations in these areas are among the main topics of interest of present day theoretical computer science. They use tools from several different mathematical disciplines, among them the one which we plan to employ in our investigations, the theory of formal languages and automata.
The study of nature-motivated computational models using methods of formal language theory was started a relatively long time ago. The introduction of Lindenmayer systems, for example, have been motivated by the process of plant development, and this study has been an important area of research ever since its beginnings. Other important topics are, for example, the theory of splicing systems, insertion/deletion systems, or test tube distributed systems based on splicing from the field of molecular computing, or models of artificial life, such as the notion of eco-grammar systems introduced by the applicant principal investigator and her co-authors in. The field of membrane systems or P systems, a recent and intensively studied area of cellular computing, uses mostly formal language theoretic tools as well.
Aims. A major characteristic of natural systems is the distributed organization of their building elements, thus distributivity is usually also an important attribute of most nature-motivated computational models. For this reason, we intend to investigate nature-motivated, in particular bio-inspired distributed computational models using tools and techniques provided by formal language and automata theory. We construct new computational models and develop existing ones, study their properties, such as their computational and descriptional complexity, robustness, the patterns and dynamics of their behavior, and the dependence of these properties on the structure, and on the way of the organization and the functioning of the system.
The study and the comparison of the properties of these computational models which are based on new principles provide two kinds of results: On one hand, they help to obtain a better understanding and a more precise description of the theoretical principles, the driving forces behind natural processes, and on the other hand they enhance and expand the mathematical theory of formal languages and automata.
In particular, we study membrane systems, or P systems, models from the area of cellular computing. The concept of a P system was introduced by Gh. Paun in 1998 as an abstract computational model based on the structure and the functioning of living cells. The area soon proved to be a successful field in natural computing.
We study P automata (membrane automata), notions combining the characteristics of conventional automata and P systems which are in interaction with their environment. The concept was introduced by E. Csuhaj-Varjú and Gy. Vaszil in 2002,, and it has received considerable international attention from researchers working in the field.
In the frame of the project, we also investigate computational models from the field of molecular computing which could be described by a general term as bio-inspired networks of language processors. Examples of these models are test tube systems based on splicing, or networks of evolutionary processors which were inspired by the process of genome development. Our aim is to obtain a more precise description of the properties of these systems and to build bridges between these research fields and other areas of formal language and automata theory.