Verification of Process Rewrite Systems in normal form

Details Verification of Process Rewrite Systems in normal form Verification of Process Rewrite Systems in normal form

2004-01-16

arxiv.org/abs/cs/0401013v1

Computer Science

Other Computer Science

53 pages, 1 figure

Scientific paper

We consider the problem of model--checking for Process Rewrite Systems (PRSs) in normal form. In a PRS in normal form every rewrite rule either only deals with procedure calls and procedure termination, possibly with value return, (this kind of rules allows to capture Pushdown Processes), or only deals with dynamic activation of processes and synchronization (this kind of rules allows to capture Petri Nets). The model-checking problem for PRSs and action-based linear temporal logic (ALTL) is undecidable. However, decidability of model--checking for PRSs and some interesting fragment of ALTL remains an open question. In this paper we state decidability results concerning generalized acceptance properties about infinite derivations (infinite term rewritings) in PRSs in normal form. As a consequence, we obtain decidability of the model-checking (restricted to infinite runs) for PRSs in normal form and a meaningful fragment of ALTL.

Affiliated with

Also associated with

No associations

Rating

Verification of Process Rewrite Systems in normal form does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Verification of Process Rewrite Systems in normal form, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Verification of Process Rewrite Systems in normal form will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-585437