×

On extensions of process rewrite systems: rewrite systems with weak finite-state unit. (English) Zbl 1271.68121

Schnoebelen, P. (ed.), Proceedings of INFINITY 2003, the 5th international workshop on verification of infinite-state systems, a satellite workshop of CONCUR 2003, Marseille, France September 2, 2003. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 98, 75-88 (2004).
Summary: Various classes of infinite-state processes are often specified by rewrite systems. We extend process rewrite systems (PRS) by R. Mayr [Inf. Comput. 156, No. 1–2, 264–286 (2000; Zbl 1046.68566)] by a 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 [P. Jančar et al., Theor. Comput. Sci. 258, No. 1–2, 409–433 (2001; Zbl 0974.68131); the last author, Electron. Notes Theor. Comput. Sci. 52, No. 1, 46–65 (2002; Zbl 1260.68279)].
For the entire collection see [Zbl 1271.68054].

MSC:

68Q42 Grammars and rewriting systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: Link