Rewriting Systems Over Indexed Multisets
Oana Agrigoroaiei, Gabriel Ciobanu · The Computer Journal · 2013
We study indexed multisets in the context of multiset rewriting systems, using indexes to capture the number of the step in which a rule is applied or an object is produced. We show that the evolution of a multiset rewriting system is accurately reflected by its indexed version and we extend this result to maximal parallelism. We analyse situations in which indexed rule application can be postponed, and introduce an equivalence relation based on such situations. We introduce the notions of cause and of causal chains, and show how adding indexes allows us to decompose evolution into independent causal chains.