Parallel Execution of Multi-set Constraint Rewrite Rules

Multi-set constraint rewriting allows for a highly parallel compu-tational model and has been used in a multitude of application do-mains such as constraint solving, agent specification etc. Rewriting steps can be applied simultaneously as long as they do not inter-fere with each other. We wish that the underlying constraint rewrite implementation executes rewrite steps in parallel on increasingly popular becoming multi-core architectures. We design and imple-ment efficient algorithms which allow for the parallel execution of multi-set constraint rewrite rules. Our experiments show that we obtain some significant speed-ups on multi-core architectures