1,721,203 research outputs found
Computing by observing: A brief survey
No full textThis paper is a brief survey of a computational paradigm called computing by observing that stresses the role of an observer in computation. The idea of the paradigm is that a computing device can be obtained by combining a basic system and an observer that transforms the trajectories of the basic system into a readable output. The paradigm has been applied in several areas: natural computing (DNA computing and membrane computing), automata and formal language theory. In general, it has been shown that simple basic systems observed by simple observers can produce that which only much more complex systems can produce. © 2008 Springer-Verlag Berlin Heidelberg
Evolution–Communication P Systems
No full textWe propose a new class of P systems that use simple evolution rules (classical evolution rules without communication targets) and symport/antiport rules (for communication). This type of P system is realistic for (at least) three different reasons: we do not have target indications in the evolution rules, we use very simple symport/antiport rules to realize communication, and we do not need objects available in the environment at the beginning of a computation. Somewhat expected, this new variant is still universal. We prove the universality in two cases: when using catalytic rules (but only one catalyst), symport/antiport rules of weight one, and two membranes, and when we use three membranes, symport/antiport rules of weight one, and no catalyst. Especially the latter result is of interest, because the catalysts were used in most universality proofs for P systems with symbol-objects. Also new is the proof technique we use: we start from programmed grammars with unconditional transfer. © Springer-Verlag Berlin Heidelberg 2003
Time and synchronization in membrane systems
No full textMembrane systems are parallel computational devices inspired from the cell functioning. Since the original definition, a standard feature of membrane systems is the fact that each rule of the system is executed in exactly one time-unit. However, this hypothesis seems not to have a counterpart in real world. In fact, in cells, chemical reactions might take different times to be exe-cuted. Therefore, a natural step is to associate to each rule of a membrane system a certain time of execution. We are interested in membrane systems, called time-free, working independently from the assigned execution time of the rules. A basic and interesting problem in time-free membrane systems consists in the synchronization of different rules, running in parallel, and having unknown execution times. Here, we present different ways to approach this problem within the framework of membrane systems. Several research proposals are also suggested
The evolutionary resilience of distributed cellular computing
Full text linkIndividual cells process environmental information relevant to their functions using biochemical processes and signalling networks that implement a flow of information from the extracellular environment, across the cell membrane to the cytoplasm in which the actual cellular computation takes place (in the form of gene expression). In many cases, the environmental information to be processed are either molecules produced by other cells or shared extracellular molecules - in this case the processing of the environmental information is a distributed, highly parallel computing process, in which cells must synchronize, coordinate and cooperate. While the ability of cells to cooperate can increase their overall computational power, it also raises an evolutionary stability issue population of cooperating cells are at risk of cheating cells invasions, cells that do not cooperate but exploit the benefits of the population. The bridge between membrane computing (as a mathematical formalization of cellular computing) and evolutionary dynamics (as mathematical formalization of natural selection) could lead to interesting insights on the evolutionary stability of cellular computing
Forbidding and enforcing in membrane computing
No full textMotivated by biochemistry and the non-deterministic reactions between molecules, the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems (fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second case the membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders. © 2003 Kluwer Academic Publishers
Experiments on the reliability of stochastic spiking neural P systems
No full textIn the area of membrane computing, time-freeness has been defined as the ability for a timed membrane system to produce always the same result, independently of the execution times associated to the rules. In this paper, we use a similar idea in the framework of spiking neural P systems, a model inspired by the structure and the functioning of neural cells. In particular, we introduce stochastic spiking neural P systems where the time of firing for an enabled spiking rule is probabilistically chosen and we investigate when, and how, these probabilities can influence the ability of the systems to simulate, in a reliable way, universal machines, such as register machines. © Springer Science+Business Media B.V. 2008
Observation of string-rewriting systems
No full textModels of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power
P systems with symport/antiport of rules
No full textMoving "instructions" instead of "data" using transport mechanisms inspired by biology is the basic idea of the computing device presented in this paper. Specifically, we propose a new class of P systems that use both evolution rules and symport/antiport rules. The idea of this kind of systems is the following: during a computation, symbol-objects (the "data") evolve using evolution rules, but they cannot be moved; on the other hand, the evolution rules (the "instructions") can be moved across the membranes using classical symport/antiport rules. We present a number of results using different combinations of evolution rules (catalytic, non-cooperative) and the weight of the symport/antiport rules. In particular, we show that using non-cooperative rules and antiports of unbounded weight makes it possible to obtain at least the Parikh set of ETOL languages. On the other hand, using catalytic rules (one catalyst) and antiports of weight 2, these system become universal. Several open problems are also presented. © J.UCS
Time-independent P systems
No full textWe introduce a class of P systems called timed P systems where to each rule is associated an integer that represents the time needed by the rule (reaction) to be entirely executed. The idea comes from cell biology where chemical reactions take certain times to be executed. In this work we are interested in a special class of P systems, called time-free, working always in the same way (i.e., always producing the same result) independently from the values associated to the execution time of their rules. Later we introduce a generalization of time-free P systems, namely clock-free P systems, where a time of execution is associated directly to each single application of the rules (in this case, different applications, even of the same rule, may take a different time to be executed). Several results are presented together with open problems and research proposals. © Springer-Verlag Berlin Heidelberg 2005
- …
