Technical Reports

The report FIMU-RS-2003-05

Process Rewrite Systems with Weak Finite-State Unit

by Mojmír Køetínský, Vojtìch Øehák, Jan Strejèek, This is a full version of the paper presented at INFINITY`03. September 2003, 23 pages.

FIMU-RS-2003-05. Available as Postscript, PDF.

Abstract:

Various classes of infinite-state processes are often specified by rewrite systems. We extend Mayr`s Process Rewrite Systems (PRS) by finite-state unit whose transition function satisfies some restrictions inspired by weak finite automata. We classify these models by their expressiveness and show how the hierarchy of new classes (w.r.t. bisimilarity) is related to both PRS hierarchy of Mayr and two other hierarchies of PRS extensions introduced in [JKM02, Str02].