Special Issue: Membrane ComputingNo Access

FURTHER RESULTS ON TIME-FREE P SYSTEMS

Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Search for more papers by this author

and

VINCENZO DEUFEMIA

Department of Mathematics and Computer Science, University of Salerno, Via Ponte don Melillo, 84084 Fisciano(SA), Italy

Search for more papers by this author

https://doi.org/10.1142/S012905410600370XCited by:10 (Source: Crossref)

Abstract

Membrane systems (currently called P systems) are parallel computing devices inspired by the structure and the functioning of living cells. A standard feature of P systems is that each rule is executed in exactly one time unit. Actually, in living cells different chemical reactions might take different times to be executed; moreover, it might be hard to know precisely such time of execution. For this reason, in [7] two models of P systems (time-free and clock-free P systems) have been defined and investigated, where the time of execution of the rules is arbitrary and the output produced by the system is always the same, independently of this time. Preliminary results concerning time-free and clock-free P system have been obtained in [6, 7, 8]. In this paper we continue these investigations by considering different combinations of possible ingredients. In particular, we present the universality of time-free P systems using bi-stable catalysts. Then, we prove that this result implies that is not possible to decide whether an arbitrary bi-stable catalytic P system is time-free. We present several results about time-free evolution-communication P systems, where the computation is a mixed application of evolution and symport/antiport rules. In this case we obtain the universality even by using non-cooperative evolution rules and antiports of weight one. Finally, we formulate several open problems.

Keywords:

AMSC: 68Q05, 68Q45, 68Q85, 02D25, 03D35

References

A. Alhazov, New Generation Computing 22(4), 299 (2004). Crossref, Web of Science, Google Scholar
I. I. Ardelean, M. Cavaliere, S. Dragoş, Computing using signals: From cells to P systems. In Technical Report 01/2004 of RGNC, Brainstorming Week on Membrane Computing 2004, University of Sevilla, Sevilla, 2004, 60–73, and Soft Computing, 9, 9 (2005) . Google Scholar
D. P. Bertsekas and J. Tsitsiklis , Parallel and Distributed Computation: Numerical Methods ( Prentice-Hall , 1989 ) . Google Scholar
P. Bottoniet al., Acta Informatica 38(10), 695 (2002). Crossref, Web of Science, Google Scholar
M. Cavaliere, Evolution–communication P systems, LNCS 2597, Membrane Computing. International Workshop, WMC-CdeA 2002 (2002), eds. Gh. Păunet al. (Springer-Verlag, Berlin, 2003) pp. 134–145. Google Scholar
M. Cavaliere, Toward asynchronous P systems, Pre-Proceedings of Fifth Workshop on Membrane Computing pp. 161–173. Google Scholar
M. Cavaliere and D. Sburlan, Time-independent P systems, LNCS 3365, Membrane Computing. International Workshop, WMC5 (), eds. G. Mauriet al. (Springer-Verlag, Berlin, 2005) pp. 239–258. Google Scholar
M. Cavaliere and D. Sburlan, Fundamenta Informaticae 64, 53 (2005). Web of Science, Google Scholar
J. Dassow and Gh. Păun , Regulated Rewriting in Formal Language Theory ( Springer-Verlag , Berlin , 1989 ) . Crossref, Google Scholar
R. Freundet al., Theoretical Computer Science 330(2), 251 (2005). Crossref, Web of Science, Google Scholar
E. Gurari , An Introduction to the Theory of Computation ( Computer Science Press , 1989 ) . Google Scholar
J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation ( Addison-Wesley , 1979 ) . Google Scholar
S. N. Krishna and A. Păun, New Generation Computing 22(4), 377 (2004). Crossref, Web of Science, Google Scholar
Gh. Păun , Membrane Computing – An Introduction ( Springer-Verlag , Berlin , 2002 ) . Crossref, Google Scholar
G. Rozenberg and A. Salomaa (eds.) , Handbook of Formal Languages ( Springer-Verlag , Berlin , 1997 ) . Crossref, Google Scholar
D. Sburlan, Clock-free P systems, Pre-Proceeding of Fifth Workshop on Membrane Computing pp. 372–383. Google Scholar