|
Tamas Roska: Analog-and-logic Cellular Wave Computers In this overview, a new cellular computing and computer paradigm is presented. Its architecture is cellular, however, unlike the cellular automaton, its data are analog spatial-temporal flows. The core of the architecture is a cellular nonlinear network (CNN) consisting of continuous valued cell dynamical systems placed on a regular spatial grid. The interactions between the dynamic cells are mainly local, within a finite sphere of influence. The protagonist elementary instruction is a solution of a PDE discretized only in space. These wave instructions are combined with binary logic in the CNN Universal Machine architecture, a universal machine on flows (including pictures and binary masks as special cases). The silicon and optical implementations will be briefly reviewed and the biological relevance is highlighted by a retinal model based on the recent discovery of the operation of the inner mammalian retina. Molecular-size new implementations and Computational Complexity issues will be briefly mentioned. New results concerning H systems and P systems We presents result concerning Splicing (or H) systems and Membrane (or P) systems. For what concern H systems we will face the problem of characterizing the class of regular languages generated by finite Paun linear splicing systems (finite initial language, finite set of rules). We consider reflexive finite splicing systems, introduced by Head (1998), finite Paun linear splicing systems in which the set R satifies a reflexive hypothesis. An already known result stated in the same paper stresses how the notion of constant, introduced by Schutzenberger (1975), is fundamental for studying these special splicing systems. In this talk we present an extension of the above-mentioned result. We completely describe the structure of regular languages generated by reflexive splicing systems, by means of a finite set of constants for the language. Since Head's splicing systems are all reflexive, as a byproduct, we characterize regular languages generated by these splicing systems. Some examples, presented at the end of the talk, will clarify the techniques and the ideas used for obtaining our results. Finally, we exhibit an example of a regular language which is generated by a finite linear splicing system, but which is not a reflexive language. For what concern P systems, we consider rewriting P systems with parallel application of evolution rules. Different kinds of parallelism methods are defined for string rewriting. The notion of deadlock is then introduced to describe situations where rules with mixed target indications are simultaneously applied to a common string. We investigate generative power of parallel P systems with respect to Lindenmayer systems, and some relations among different types of parallel P systems with or without deadlock. Carriers and Counters. P systems with Carriers vs. (Blind) Counter Automata Membrane systems (P systems) are a computational framework inspired by natural membranes. Composed of a set of hierarchically nested membranes, objects evolve within each membrane according to specific rules, and these objects may travel from one membrane into another under certain conditions. After their introduction by Paun, the field has been rapidly growing.
Here we consider membrane systems with carriers,
introduced
by Martin-Vide,
Paun, and
Rozenberg.
Objects are abstract symbols that cannot
be deleted, copied, or changed in any way.
A finite number
of This can be improved to a single membrane, two carriers and (again) three passengers per carrier. We view the single membrane as a counter automaton (register machine) where the contents of the membrane code state and counter values. A single carrier shuttles in and out of the membrane to change state and to update counter values. Another carrier is instrumental in performing the zero tests to the counter values.
Our construction suggests
that the key feature of P~systems
responsible for universality is the requirement of
maximal parallelism.
Indeed, we show
that carrier P systems
without maximal parallelism in
their computational steps
can be simulated by a
Some techniques for scalable integrated DNA computing Microflow systems offer unique possibilities for integrating DNA Computing. An overview of some techniques for improving the scalability and programmability of DNA Computing in microfluidic systems is presented. The possibilities and limitations of valve-based systems are outlined and compared with valve free systems. In particular, recent work on developing a valve-free electronically programmable DNA Computer via hybrid BioModules will be discussed. Limits on our ability to scale electrode controlled biomolecular processing are analysed and principles for extending electrode control over DNA selection and transfer into the range of thousands to millions are outlined. This work builds on previous valve-free integration of DNA Computing in microflow systems [McCaskill, J.S., Optically Programming DNA Computing in Microflow Reactors. Biosystems, 2001. 59(2): p. 125-138] but makes use of additional non-magnetic techniques. Constructing a Universal P System P systems were originally introduced as distributed parallel computability models. They are bases upon a hierarchically ordered, finite cell-structure. They consist of several cell-membranes embedded in the main membrane called the skin. A P system which takes as input a P system, and simulates it is called a direct Universal splicing P system. In this talk I will discuss the construction of a Universal P system which can simulate a given P system, provided as input. S. Verlan: Results on some splicing-based systems We will consider the time-varying distributed H systems (TVDH systems) introduced in 1997 by G. Paun and enhanced time-varying distributed H systems (ETVDH systems) introduced by M. Margenstern and Yu. Rogozhin in 2000. The main results for these systems are the following: TVDH systems of degree 1 (with 1 component) and ETVDH systems of degree 2 can generate any RE language. ETVDH systems of degree 1 can generate only regular languages. While the proof of the first two results is "sequential" there is an interest for finding "parallel" proofs which fit better the parallel behaviour of DNA recombination. We will present such proofs. Thus we not only improved the previous results but we closed this problem because these results can not be improved further. We shall also add that the proof introduces new ideas which can be used in a variety of splicing systems. M. Margenstern: A tentative additional frame for DNA computing and P systems In this talk, we indicate a very simple algorithmic method which allows to implement cellular automata in hyperbolic spaces, and which consists in locating the tiles of regular tilings by an appropriate coordinate system. We shall indicate the reasons according to which we are convinced that hyperbolic geometry can give a frame for some kinds of DNA computations and why also it seems to us that it can be a natural setting for P systems. The reasons come from some properties of the hyperbolic geometry itself which, perhaps, gives a better setting for the description of life itself, especially its forms. Other reasons are the ro^le which is played by abstract structures and languages both in hyperbolic geometry and in DNA computing. A few teams are already interested in this approach. There is enough room for this direction for all of us who would like to go on such a way. On Three Classes of Automata-Like P Systems We consider the three classes of (string or number) accepting P systems proposed so far, namely the P automata of E. Csuhaj-Varju, Gy. Vaszil, the variant introduced by M. Madhu, and the related machinery of R. Freund, M. Oswald. All three are based on symport/antiport rules -- with certain specific differences in the first two cases. For slight variants of the first two classes we prove that any recursively enumerable language can be recognized by systems with only two membranes (this considerably improves the result of Csuhaj-Varju, Vaszil, where systems with seven membranes were proved to be universal). For the third class we investigate the initial mode of accepting strings (the strings are introduced into the system, symbol by symbol, at the beginning of a computation), and we prove that such devices (even with only one membrane) can recognize all recursively enumerable languages in the cases when the rules are applied in a conditional manner (having permitting or forbidding conditions in the form of symbols which should be present/absent), when using priorities, and when having probabilities associated with rules. The conditions when we can pass from systems with priorities to systems with probabilities are characterized. For languages on the one-letter alphabet these controls on the use of rules are not necessary. We also investigate the power of systems of a small size (as the number of membranes and length of symport and antiport rules), mainly in comparison with classes of languages from the Chomsky hierarchy. Some open problems are also formulated. First Approach of the Specification of a Transition P systems Machine Language for a Membrane Processor
This paper presents a first approach to the design of a machine
language for Transition P systems able to be implemented in a
digital processor named P Automata on Finite and Infinite Words
Membrane systems were introduced by Gheorghe Paun
in [6] in 1998; since then many variants of
membrane systems (then also called References
Circularity and other invariants of gene assembly in ciliates
Ciliates (an ancient group of single cell organisms) have two sorts
of nuclei with different functionalities: the micronucleus and the macronucleus.
After the cell mating the micronuclear genes are converted into the
macronuclear genes in the process called {\em gene assembly}.
This is one of the most complex examples of DNA processing known
in any organisms, and it is fascinating from the computational point
of view. This paper continues the investigation of gene assembly in the framework of three molecular
operations: New Results on P Automata, Accepting P Systems with Only Communication The notion of P automata, introduced in [1], attempts to build a bridge between P systems and the traditional concept of automata. A P automaton is a P system using communication rules only and describing languages through the multiset sequences entering the skin membrane during its functioning, that is, multiset sequences accepted by the system. The accepting power of P automata was studied in [1,2], showing that all recursively enumerable languages can be obtained as the image of the language of the accepted multiset sequences. Now we focus on the direct characterization of these languages. We demonstrate certain properties of the accepted languages by giving conditions on the order and the number of occurrences of the symbols of their words. We also study the way of using constraints on the different type (sequential or maximal parallel) of application of the different kinds (one way or two way communication) of rules. Besides the usual constraints given at the level of the rules, we propose and study the effect of global conditions when the possibility of communication (rule application) in a membrane depends on the value of a function evaluating the whole contents of the membrane. By using global constraints, the work of the automaton can be based on quantitative conditions, an ability that is not present when the constraints are tied to the individual rules. References
Mathematical Models of Molecular-Genetic Triggers It is proved that the transcription regulation process of gene expression can be represented as a molecular-genetic trigger (MGT). MGT is a self-organizing structure with two stable states (true and false), it can switch from one stable state to another. These two stable states of MGT correspond to the active and passive (repressed) state of genes, respectively. MGT, are successfully investigated in molecular biology since the well-known work of Jacob and Monod. On the basis of experimental data mathematical trigger models (systems of differential equations) of concrete genetic structures (LexA RecA dependent recombination trigger system of Escherichia coli; Trigger model of gene expression regulation of ts-mutant of oncogene Src;) are investigated. A living cell represents a complex biosystem where processes of self-regulation and self-organization occur due to feedbacks, nonlinear properties of system and cooperative actions of objects constitute the biosystem (proteins, enzymes, mRNA, repressors, activators, etc.). It is known that the transcriptional regulation of gene expression plays a fundamental role in cell life and in its response to environmental stimuli. Thus, as a cell reacts on the exogenous and the endogenous factors (temperature, UV radiation, pH, concentration of repressors or activators, etc.), considered as input signals, we can control and direct the intercellular processes (the process of gene expression) on the basis of mathematical and stochastic models of MGT. MGTs (i.e., finite deterministic automata) being similar to transistors can be of several types in dependence of genetic constructions of cells. It is shown that they can fulfill logical functions OR, XOR, NOT AND, AND. The temperature and pH - dependent switching of trigger systems controlled by regulatory enzymes are analyzed. It is shown that when either exogenous or endogenous factors exceed a critical value in the molecular-genetic system the hysteresis, bistability solutions and the dynamic memory can appear. The role of fluctuations of temperature and of concentration of protons [H+] in the molecular-genetic system it is taken into consideration. The stationary density of probabilities (i.e. real values of input/output signals), kinetic potentials as function of different values of temperature, pH or intensity of fluctuations are obtained. The numerical evaluations of switching time of genes from one stable state to an other one (i.e., computation time) for stochastic system are obtained by using the stochastic formalism of Langevin and Fokker - Plank equations. While increasing the temperature (or pH) near to the bifurcation point in which the activity of genes (for examples, Src oncogene) falls down then the switching time of genetic system from false state into true state suddenly decreases (and conversely). The role of fluctuation processes for the destruction of dynamic memory (trigger effect) is investigated. The molecular neuron and neural network realization Universal Turing machine is a notional computing machine that stimulated work leading to the development of modern computers. The Turing machine operates on finite sequences of symbols by scanning a data type. The striking analogy to information-encoding biochemical reactions on information-carrying molecules was inspired to apply this methodology in neural networks. The essential feature of such approach is hybridization of pairs of complementary DNA strings and possibility to represent highly parallel selective operations, which can enable creating alternative, neural architectures. We describe our original model of molecular neural network based on DNA computing paradigm. During computation appropriate molecules are chosen, each specifying one of the finite number of initial states or processing elements. We present not only our own DNA lattices, but also the molecular neural cube structure. The concept is illustrated by detecting the final state through one string solution. It is provided that presented neural networks may be connected to perform the molecular inference systems.
|