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].