An Application of Multiset to Deterministic P Systems with Nested Rule Prioritization and Membrane Preservation
Chinedu M. Peter
Vivian O. Ike
Abstract
This paper begins with a mathematical analysis of multisets as a formal apparatus for computation: we give precise definitions, describe multiset algebra (union, intersection, difference, complementation and additive union), present the vector interpretation of multisets and Parikh-style mappings, and examine properties of multiset rewriting systems. Building on that analysis, we show how multisets can be used to encode integers (positive and negative) in a membrane system in a uniform way. Negative values being represented by an appropriate placement of multiplicities across membrane systems with only two membranes, and how algebraic properties are used in the correct design of rewriting rules. Using this multiset foundation, we construct P systems for integer arithmetic (addition, subtraction, multiplication and division) that preserve membrane structure (i.e., without dissolution) and operate under nested weak, strong and dependency priority relations. Worked examples illustrate how the multiset analyses are used in rule priorities and how priorities control the flow of computation to guarantee correctness and termination across all the cases presented.
References