Defining and executing P systems with structured data in K. (English) Zbl 1196.68084

Corne, David Wolfe (ed.) et al., Membrane computing. 9th international workshop, WMC 2008, Edinburgh, UK, July 28–31, 2008. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-540-95884-0/pbk). Lecture Notes in Computer Science 5391, 374-393 (2009).
Summary: K is a rewrite-based framework proposed for giving formal executable semantics to programming languages and/or calculi. K departs from other rewrite-based frameworks in two respects: (1) it assumes multisets and lists as built-in, the former modeling parallel features, while the latter sequential ones; and (2) the parallel application of rewriting rules is extended from non-overlapping rules to rules which may overlap, but on parts which are not changed by these rules (may overlap on “read only” parts). This paper shows how P systems and variants can be defined as K (rewrite) systems. This is the first representation of P systems into a rewrite-based framework that captures the behavior (reaction steps) of the original P system step-for-step. In addition to providing a formal executable semantic framework for P systems, the embedding of P systems as K systems also serves as a basis for experimenting with and developing new extensions of P systems, e.g., with structured data. A Maude-based application for executing P systems defined in K has been implemented and experimented with; initial results show computational advantages of using structured objects in P systems.
For the entire collection see [Zbl 1167.68002].


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q42 Grammars and rewriting systems


ML ; KOOL; Maude; K Prover
Full Text: DOI


[1] Alberts, B., Bray, D., Lewis, J., Raff, M., Roberts, K., Watson, J.D.: Molecular Biology of the Cell, 3rd edn. Garland Publishing, New York (1994)
[2] Andrei, O., Ciobanu, G., Lucanu, D.: Structural operational semantics of P systems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 31–48. Springer, Heidelberg (2006) · Zbl 1135.68400
[3] Andrei, O., Ciobanu, G., Lucanu, D.: Expressing control mechanisms of membranes by rewriting strategies. In: Hoogeboom, H.J., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2006. LNCS, vol. 4361, pp. 154–169. Springer, Heidelberg (2006) · Zbl 1187.68223
[4] Andrei, O., Ciobanu, G., Lucanu, D.: Operational semantics and rewriting logic in membrane computing. Electr. Notes Theor. Comput. Sci. 156, 57–78 (2006) · Zbl 1273.68201
[5] Andrei, O., Ciobanu, G., Lucanu, D.: A rewriting logic framework for operational semantics of membrane systems. Theoretical Computer Sci. 373, 163–181 (2007) · Zbl 1111.68064
[6] Banatre, J.-P., Coutant, A., Le Metayer, D.: A parallel machine for multiset transformation and its programming style. Future Generation Computer Systems 4, 133–144 (1988)
[7] Berry, G., Boudol, G.: The chemical abstract machine. Theoretical Computer Sci. 96, 217–248 (1992) · Zbl 0747.68013
[8] Cardelli, L.: Brane calculi. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 257–278. Springer, Heidelberg (2005) · Zbl 1088.68657
[9] Ciobanu, G., Păun, G., Stefănescu, G.: P transducers. New Generation Computing 24, 1–28 (2006) · Zbl 1103.68050
[10] Clavel, M., Duran, F., Eker, S., Lincoln, P., Marti-Oliet, N., Meseguer, J., Quesada, J.F.: Maude: specification and programming in rewriting logic. Theoretical Computer Sci. 285, 187–243 (2002) · Zbl 1001.68059
[11] Davis, M., Sigal, R., Weyuker, E.J.: Computability, Complexity, and Languages, 2nd edn. Morgan Kaufmann, San Francisco (1994)
[12] Frisco, P.: The conformon-P system: A molecular and cell biology-inspired computability model. Theoretical Computer Sci. 312, 295–319 (2004) · Zbl 1070.68040
[13] Hills, M., Rosu, G.: KOOL: An application of rewriting logic to language prototyping and analysis. In: Baader, F. (ed.) RTA 2007. LNCS, vol. 4533, pp. 246–256. Springer, Heidelberg (2007) · Zbl 05222816
[14] Hills, M., Serbanuta, T., Rosu, G.: A rewrite framework for language definitions and for generation of efficient interpreters. Electr. Notes Theor. Comput. Sci. 176, 215–231 (2007) · Zbl 1279.68116
[15] Meseguer, J.: Conditioned rewriting logic as a united model of concurrency. Theoretical Computer Sci. 96, 73–155 (1992) · Zbl 0758.68043
[16] Meredith, P., Hills, M., Rosu, G.: A K Definition of Scheme. Technical report UIUCDCS-R-2007-2907 (October 2007)
[17] Milner, R.: A theory of type polymorphism in programming. J. Computer System Sci. 17, 348–375 (1978) · Zbl 0388.68003
[18] Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989) · Zbl 0683.68008
[19] Păun, A., Păun, G.: The power of communication: P systems with symport/antiport. New Generation Computing 20, 295–306 (2002) · Zbl 1024.68037
[20] Păun, G.: Computing with membranes. J. Computer and System Sci. 61, 108–143 (2000) · Zbl 0956.68055
[21] Păun, G.: P systems with active membranes: Attacking NP-complete problems. J. Automata, Languages and Combinatorics 6, 75–90 (2001) · Zbl 0970.68066
[22] Păun, G.: Membrane Computing. An Introduction. Springer, Heidelberg (2002)
[23] Rosu, G.: K: A rewriting-based framework for computations – Preliminary version. Technical Report UIUCDCS-R-2007-2926, Department of Computer Science, University of Illinois. Previous versions published as technical reports UIUCDCS-R-2006-2802 in 2006, UIUCDCS-R-2005-2672 in 2005. K was first introduced in the context of Maude in Fall 2003 as part of a programming language design course (report UIUCDCS-R-2003-2897 (2007), http://fsl.cs.uiuc.edu/k
[24] The Web Page of Membrane Computing, http://ppage.psystems.eu/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.