Rewrite Systems with Constraints
Jan Strejček · Electronic Notes in Theoretical Computer Science · 2002
We extend a widely used concept of rewrite systems with a unit holding a kind of global information which can influence and can be influenced by rewriting. The unit is similar to the store used in concurrent constraint programming, and can be also seen as a special (weak) state unit. We present how this extension changes the expressive power of rewrite systems classes which are included in Mayr's PRS hierarchy [8]. The new classes (fcBPA, fcBPP, fcPA, fcPAD, fcPAN, fcPRS) are described and inserted into the hierarchy.