Rewrite Systems with Constraints

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	STREJČEK Jan
Year of publication	2001
Type	Article in Proceedings
Conference	EXPRESS'01 the 8th International Workshop on Expressiveness in Concurrency
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://www.elsevier.nl/locate/entcs/volume52.html
Field	Computer hardware and software
Keywords	(rewrite) transition system; concurrency; partial information; bisimulation equivalence; language expressibility
Description	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.
Related projects:	Infinite state concurrent systems - models and verification Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing