Sequential and maximally parallel multiset rewriting: reversibility and determinism

Abstract

We study reversibility and determinism aspects and the strong versions of these properties of sequential multiset processing systems and of maximally parallel systems, from the computability point of view. In the sequential case, syntactic criteria are established for both strong determinism and strong reversibility. In the parallel case, a criterion is established for strong determinism, whereas strong reversibility is shown to be decidable. In the sequential case, without control all four classes—deterministic, strongly deterministic, reversible, strongly reversible—are not universal, whereas in the parallel case deterministic systems are universal. When allowing inhibitors, the first and the third class become universal in both models, whereas with priorities all of them are universal. In the maximally parallel case, strongly deterministic systems with both promoters and inhibitors are universal. We also present a few more specific results and conjectures.