Reversibility in Parallel Rewriting Systems

Bogdan Aman (Romanian Academy, Romania)

Gabriel Ciobanu ("A.I.Cuza" University, Romania)

Abstract: This paper represents a study of reversibility in parallel rewriting systems over multisets. It emphasizes the controlled reversibility for a particular case of parallel rewriting systems given by membrane systems, a formalism inspired by the cell activity. We define reversible membrane systems in which the scenarios based on regular expressions are able to control the direction (forward or backward) of the evolution. The backward computation is triggered by a special symbol ae introduced into the system. Several results concerning the evolution of membrane systems and reversible membrane systems are provided, opening new research opportunities.

Keywords: controlled reversibility, membrane computing

Categories: F.1.1, F.4.2, F.4.3