Rewriting Semantics of P Systems

People

Strategy-based Rewriting Logic Semantics of P Systems

Strategy-based Rewriting Logic is a combination between rewrite theories, strategies, and strategy controllers. The intuition behind a strategy controller is that it decides which strategy is applied in the current state. We refer to the set of evolution rules of a membrane as a control-free membrane. Similarly, by a control-free membrane system we refer to the set of evolution rules of a membrane system. A control-free membrane (system) is specified by a rewrite theory in RWL. Based on the current state, a strategy controller produces a strategy (called evolution strategy) describing the possibly next one-step evolutions.

Download

The archive srl_membrane.zip includes the following files:

_strategy.maude - the API for Maude Strategy Language,
membrane.maude - the strategy-based rewrite theory describing membranes and the interface,
a set of several examples of membrane systems (exi.maude).

In order to run examples, start the Maude system (version 2.3 or later), load full-Maude, load membrane.maude (this automatically loads _strategy.maude), and then load examples one by one.

Publications

Strategy-Based Proof Calculus for Membrane Systems by O. Andrei and D. Lucanu. Proceedings of WRLA 2008, pages 17-34, 2008. To appear in ENTCS.
Strategy-Based Rewrite Semantics for Membrane Systems Preserves Maximal Concurrency of Rewrite Actions by D. Lucanu. 7th International Workshop on Reduction Strategies in Rewriting and Programming (WRS'08), pages 16-30, 2008. To appear in ENTCS.
Rewriting Logic-based Semantics of Membrane Systems and the Maximal Concurrency by D. Lucanu. Proceedings of Prague International Workshop on Membrane Computing, pages 23-34, 2008.

Rewriting Logic Semantics of P Systems

We have defined an operational semantics of a basic class of P systems and we implemented it using rewriting logic. The structure and behavior of a P system is described by means of an executable specifications in Maude, a software system supporting rewriting and equational logic. We can verify properties of the system expressed as linear temporal logic formulas by using the model checker implemented in Maude.

Download

The algebraic specifications for the syntax and the semantics are available at this page.

Demo

We provide some examples with complete details of their execution in Maude and analysis.

Publications

A rewriting logic framework for operational semantics of membrane systems by Oana Andrei, Gabriel Ciobanu and Dorel Lucanu. Theoretical Computer Science 373 (2007), pp. 154-169.
[DOI]
Expressing Control Mechanisms in P Systems by Rewriting Strategies by Oana Andrei, Gabriel Ciobanu, and Dorel Lucanu. In H. Hoogeboom, G. Paun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, International Workshop, WMC7, Leiden, The Netherlands, 2006, Revised, Selected and Invited Papers, vol. 4361 of LNCS, pages 154-169. Springer, 2006.
[DOI]
Strategies and Tactics in Operational Semantics by Oana Andrei, Gabriel Ciobanu, and Dorel Lucanu. Technical Report TR 06-01, "Al.I.Cuza" University of Iasi, Faculty of Computer Science, 2006.
[pdf]
Operational Semantics and Rewriting Logic in Membrane Computing by Oana Andrei, Dorel Lucanu, and Gabriel Ciobanu. In Proceedings of the Second Workshop on Structural Operational Semantics (SOS 2005), volume 156, pages 57-78. ENTCS, 2006.
[DOI]
Structural Operational Semantics of P Systems by Oana Andrei, Gabriel Ciobanu, and Dorel Lucanu. In R. Freund, G. Paun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised, Selected and Invited Papers, vol. 3850 of LNCS, pages 31-48. Springer, 2005.
[DOI]
Executable Specifications of P Systems by Oana Andrei, Gabriel Ciobanu, and Dorel Lucanu. In G. Mauri, G. Paun, M. J. Pérez-Jiménez, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, 5th International Workshop, WMC 2004, Milan, Italy, June 14-16, 2004, Revised Selected and Invited Papers, vol. 3365 of LNCS, pages 126-145. Springer, 2004.
[DOI]

Links to related web pages

If you have comments or questions, please contact [andrei _ at _ loria dot fr]. Thank you.

Last modification: 31 August 2008